Задание 9. Подсчёт путей по схеме дорог — теория и разбор

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

Что нужно знать

Схема дорог — это граф: города — точки (вершины), дороги — стрелки между ними (рёбра). Все дороги односторонние — двигаться можно только по направлению стрелки, и в схемах этого задания нет способа вернуться туда, откуда пришёл (нет циклов).

Способ решения — последовательный подсчёт: в каждом городе записываем, сколько РАЗНЫХ путей ведёт туда из города-старта. Начинаем со старта (там всегда 1 — «стоять на месте»), а дальше для каждого следующего города складываем числа всех городов, из которых в него ведёт прямая дорога.

Число путей до города — это сумма чисел всех городов, откуда в него ведёт прямая дорога, а не единица за каждую дорогу: если в город ведут две дороги из городов с числами 3 и 2, то в него ведёт 3 + 2 = 5 путей, а не 2.

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

Разбор примера

Схема дорог связывает города A, B, C, D, E, F. Все дороги — одностороннее движение, в направлении, указанном стрелками:

A→B, A→C, B→D, B→E, C→D, C→F, D→F, E→F.

Сколько существует различных путей из города A в город F?

Как думать. Идём по схеме от A и в каждом городе подписываем число путей до него — сумму чисел городов, из которых есть прямая дорога сюда.

Как решить в Python

Тот же процесс — обычная динамика на графе: идём по городам в порядке, где источники уже посчитаны, и складываем:

edges = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['D', 'F'],
    'D': ['F'],
    'E': ['F'],
    'F': [],
}
order = ['A', 'B', 'C', 'D', 'E', 'F']  # топологический порядок — источники раньше целей

count = {v: 0 for v in order}
count['A'] = 1
for v in order[1:]:
    count[v] = sum(count[u] for u in order if v in edges[u])

print(count['F'])  # 4

Такой код особенно полезен, когда городов много и держать в голове порядок подсчёта становится сложно — важно только один раз правильно переписать схему в список рёбер.