Задание 9. Пути с условием: через город и в обход города — теория и разбор

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

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

Если нужно посчитать пути из A в конечный город, проходящие через промежуточный город X, задачу удобно разбить на две части:

(число путей из A в X) × (число путей из X до конца)

Это работает, потому что дорога не образует циклов: путь через X — это сначала путь до X, а потом отдельный путь от X дальше, и любую комбинацию «первая половина + вторая половина» можно взять независимо.

Пути, проходящие через X, и пути, не проходящие через X, вместе составляют вообще все пути — поэтому «в обход X» считать отдельно не обязательно: достаточно вычесть число путей через X из общего числа путей.

Формула для двух вариантов задания: путей через X = (путей A→X) × (путей X→конец); путей в обход X = (всего путей A→конец) − (путей через X).

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

Схема дорог связывает города A, B, C, D, E, F, G одностороннего движения:

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

Сколько существует путей из города A в город G, проходящих через город D?

Как думать. Считаем отдельно число путей от A до D и число путей от D до G, а затем перемножаем — потому что каждый путь A→D можно свободно продолжить любым путём D→G.

Как решить в Python

edges = {
    'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'],
    'D': ['F'], 'E': ['F', 'G'], 'F': ['G'], 'G': [],
}
order = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

def count_paths(start, edges, order):
    idx = order.index(start)
    sub_order = order[idx:]
    count = {v: 0 for v in sub_order}
    count[start] = 1
    for v in sub_order[1:]:
        count[v] = sum(count[u] for u in sub_order if v in edges.get(u, []))
    return count

a_to_d = count_paths('A', edges, order)['D']
d_to_g = count_paths('D', edges, order)['G']
print('через D:', a_to_d * d_to_g)  # 2

total = count_paths('A', edges, order)['G']
print('всего A->G:', total)          # 4
print('в обход D:', total - a_to_d * d_to_g)  # 2