Другие вопросы о путях

В подборках спрашивают не только кратчайший путь: сколько всего путей, какой путь самый длинный, сколько в пути рёбер. Нужна ли для каждого вопроса своя идея?

Нет, функция та же. Меняются три места: что вернуть в цели, что вернуть в тупике и как собрать ответы соседей. Остальное — словарь из файла, перебор стрелок, @cache — не трогаем.

Значение в тупике — всегда «худшее, что может быть» для этого вопроса: оно не должно выиграть сравнение. Для минимума это ∞, для максимума −∞, для суммы — 0: путь в тупик в число путей до цели не входит. Разберём каждый вопрос на учебном графе.

Сколько путей ведёт из 1 в 100?

Каждый путь из v начинается какой-то стрелкой, поэтому число путей из v — сумма чисел путей из концов её стрелок. В цели путь один — пустой, «уже пришли». Ноль в цели всё бы обнулил: любая сумма нулей — ноль.

from functools import cache graph = {}for line in open("23.txt"):    a, b, w = line.split()    a, b, w = int(a), int(b), float(w)    if a not in graph:        graph[a] = []    graph[a].append((b, w))  @cachedef count(v):    if v == 100:        return 1    total = 0    for u, w in graph.get(v, []):        total += count(u)    return total  print(count(1), count(6))

Из 7 и из 4 к цели ведёт по одному пути, из 1 — 1 + 1 + 1 = 3: через 7, через 4 и напрямую. Из 6 — путь через 7 и три пути через 1, всего 4.

Путей бывают миллиарды, но Python считает целые числа без переполнения, а @cache не даёт перебирать их по одному. Число путей через ребро a → b — произведение: число путей до a, умноженное на число путей от b. Каждый путь до a можно склеить с каждым путём от b.

Какой путь из 1 в 100 самый длинный?

Тот же расчёт с max вместо min. А в тупике теперь −∞ — иначе путь, упёршийся в тупик, мог бы победить.

@cachedef longest(v):    if v == 100:        return 0    best = float("-inf")    for u, w in graph.get(v, []):        best = max(best, w + longest(u))    return best  print(longest(1), longest(6))

Из 1 самый длинный путь — прямая стрелка 1 → 100 за 12.0, из 6 — 6 → 1 → 100 за 13.0. Если бы из 1 вела стрелка в тупик весом 20, то с нулём в тупике ответ стал бы 20 — длина пути, который до 100 не доходит. С −∞ такая стрелка никогда не выигрывает максимум.

Бывает и другой вопрос: самый длинный путь из вершины до любого тупика. Тогда цели нет, и ноль возвращают как раз в тупике — там, где путь закончился:

@cachedef to_dead_end(v):    if v not in graph:        return 0    best = float("-inf")    for u, w in graph[v]:        best = max(best, w + to_dead_end(u))    return best  print(to_dead_end(6))

Из 6 это 6 → 1 → 100 → 12: 1.0 + 12.0 + 1.0 = 14. Тупиков в этом графе один — вершина 12.

Из какого наименьшего числа рёбер может состоять путь из 1 в 100?

Это тот же кратчайший путь, только каждое ребро весит 1: вместо w прибавляем 1. Веса из файла читаем, как обычно, но не используем.

@cachedef fewest(v):    if v == 100:        return 0    best = float("inf")    for u, w in graph.get(v, []):        best = min(best, 1 + fewest(u))    return best  print(fewest(1), fewest(6))

Из 1 хватает одного ребра — 1 → 100, из 6 нужно два: 6 → 7 → 100. Наибольшее число рёбер — тот же код с max и −∞ в тупике: из 1 это 2, из 6 — 3.

• Что меняетсязначение в цели, в тупике и как собрать ответы
• Число путейв цели 1, в тупике 0, сумма
• Через ребро a → bпутей до a × путей от b
• Самый длинный путьmax, в тупике −∞
• До любого тупикацели нет, 0 в тупике, max
• Число рёбервместо веса прибавляем 1