5 Способ 2 — рекурсия с запоминанием
Способ 2 — рекурсия с запоминанием
Второй способ — короче и ближе к тому, как мы думаем о путях. Введём функцию f(curr, end) — длина кратчайшего пути из вершины curr в конечную вершину end. Тогда:
если мы уже в конце (
curr == end) — идти никуда не нужно, длина 0;если из
currне выходит ни одного ребра (тупик, не финиш) — до конца отсюда не добраться, возвращаем «бесконечность» (большое число);иначе перебираем все рёбра
curr → toвесомwи берём минимум изw + f(to, end)— то есть «шаг по ребру плюс кратчайший путь дальше».
Чтобы не считать одну и ту же вершину много раз (иначе перебор разрастается), навешиваем запоминание результатов декоратором @lru_cache.
from collections import defaultdict
from functools import lru_cache
d = defaultdict(list) # список смежности: из вершины -> [ [куда, вес], ... ]
for s in open("23.txt"):
frm, to, w = [float(x) for x in s.split()]
d[frm].append([to, w]) # добавляем ребро frm -> to весом w
@lru_cache(None) # запоминаем уже посчитанные вызовы
def f(curr, end):
if curr == end: # дошли до конца — дальше идти не нужно
return 0
if curr not in d: # из curr нет рёбер — тупик
return 10**8
return min(w + f(to, end) for to, w in d[curr]) # лучший из ходов по рёбрам
print(int(f(1, 100))) # целая часть кратчайшего пути 1 -> 100Разберём по частям:
d— список смежности:d[frm]хранит все рёбра, выходящие из вершиныfrm, в виде пар[куда, вес].defaultdict(list)избавляет от проверок «а есть ли уже такой ключ».f(curr, end)— рекурсивно спрашивает у соседей, за сколько они доводят до конца, и выбирает лучший вариант.@lru_cache(None)— кэш: каждыйf(curr, end)считается один раз, потом берётся из памяти. Без него на большом графе рекурсия была бы слишком медленной.
📌 Почему рекурсия не зациклится Граф в задании 23 ациклический (это сказано в условии) — по стрелкам нельзя вернуться в уже пройденную вершину. Поэтому рекурсия всегда движется «вперёд, к финишу» и обязательно завершается. На графе с циклом такой способ зациклился бы — но здесь циклов нет. |
📌 Тонкость с типами вершин В коде номера вершин читаются как |
Оба способа на файле из примера печатают 7 — ответ один и тот же. Выбирай тот, что понятнее: Беллман–Форд короче по идее, рекурсия — нагляднее по смыслу «путь = шаг плюс путь дальше».