Задание 4: анализ схемы дорог и кратчайший путь

Считаем пути по схеме дорог и находим кратчайший — это задание №4.

Граф — это схема из точек (вершин) и линий (рёбер), моделирующая дороги, связи или маршруты.

Что проверяет задание 4

В задании 4 даётся схема дорог между пунктами. Спрашивают одно из двух: сколько существует разных путей из A в B, либо какова длина кратчайшего пути. Оба типа решаются аккуратной расстановкой чисел прямо на схеме — без зубрёжки сложных алгоритмов.

Подсчёт числа путей

Если дороги односторонние (идут «слева направо» по схеме), число путей считают так:

В начальную вершину пишем 1.
В каждую следующую вершину пишем сумму чисел тех вершин, из которых в неё ведут стрелки.
Число в конечной вершине — ответ.

Пример. Из A стрелки в B и C; из B в D; из C в D; из D в E. Сколько путей из A в E?

A=1
B = A = 1
C = A = 1
D = B + C = 2
E = D = 2
Ответ: 2 пути (A-B-D-E и A-C-D-E)

Тот же подсчёт легко автоматизировать: идём по вершинам в правильном порядке и в каждую кладём сумму входящих. Проверим на чуть большем графе:

# стрелки графа (односторонние, слева направо)
edges = [("A","B"), ("A","C"), ("B","D"), ("C","D"),
         ("C","E"), ("D","F"), ("E","F")]
order = ["A","B","C","D","E","F"]

ways = {v: 0 for v in order}
ways["A"] = 1
for v in order:
    for u, w in edges:
        if w == v:                  # стрелка ведёт в v
            ways[v] += ways[u]      # прибавляем пути до u
for v in order:
    print(v, "=", ways[v])
print("Путей A->F:", ways["F"])

Вывод:

A = 1
B = 1
C = 1
D = 2
E = 1
F = 3
Путей A->F: 3

Разберём: в D приходят пути из B (1) и C (1) — итого 2; в E приходит только из C — 1; в F приходят из D (2) и E (1) — итого 3. На бумаге вы делаете ровно это: подписываете число у каждой вершины слева направо.

Кратчайший путь

Когда у дорог есть длины, ищут путь с наименьшей суммой длин. Идея та же — расставлять числа, но теперь в каждой вершине пишем минимальное расстояние от старта:

В старте — 0.
Для каждой вершины расстояние = минимум по всем входящим дорогам из (расстояние соседа + длина дороги).
Повторяем, пока числа не перестанут меняться.

Пример. Дороги: A–B (3), A–C (4), B–D (2), C–D (5), D–E (3), C–E (8). Найти кратчайший путь A→E.

INF = float("inf")
edges = {("A","B"):3, ("A","C"):4, ("B","D"):2,
         ("C","D"):5, ("D","E"):3, ("C","E"):8}
nodes = ["A","B","C","D","E"]

dist = {x: INF for x in nodes}
dist["A"] = 0
# Несколько проходов, пока расстояния обновляются
for _ in range(len(nodes)):
    for (u, v), w in edges.items():
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w

for n in nodes:
    print(n, "=", dist[n])
print("Кратчайший A->E:", dist["E"])

Вывод:

A = 0
B = 3
C = 4
D = 5
E = 8
Кратчайший A->E: 8

Разберём: до D можно дойти двумя способами — через B (3+2=5) или через C (4+5=9). Берём минимум — 5. До E: через D (5+3=8) или напрямую из C (4+8=12). Минимум — 8. Кратчайший путь A→B→D→E длиной 8.

Как считать вручную на экзамене

На бумаге это делается быстро: подписывайте число у каждой вершины. Если нашли путь короче — зачёркивайте старое число и пишите новое. Двигайтесь от старта «волной», обрабатывая вершины, у которых уже известны все входящие.

Типичные ошибки

При подсчёте путей перемножают числа вместо сложения.
Для кратчайшего пути берут максимум вместо минимума.
Пропускают одну из входящих дорог в вершину.
Считают путь A→E, когда в условии спрашивали, например, A→D — читайте конечную точку внимательно.

Итог

Число путей: в старте 1, дальше — сумма входящих.
Кратчайший путь: в старте 0, дальше — минимум (расстояние соседа + длина дороги).
Расставляйте числа прямо на схеме, обновляя при нахождении лучшего варианта.