Статья Автор: Деникина Н.В., Деникин А.В.

Кратчайший путь в графе: Форд–Беллман

Алгоритм Форда–Беллмана

Идея: у каждой вершины есть рекорд

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

Бесконечность

В питоне есть настоящая бесконечность: float('inf'). Она больше любого числа, а прибавление к ней ничего не меняет. Значит, если рекорд вершины i ещё бесконечность, то dist[i] + w тоже бесконечность и min ничего не испортит.

Бесконечность избавляет от проверки достижимости.

Одно ребро — одна попытка улучшить рекорд

Берём ребро из i в j весом w и рассуждаем: до i я дохожу за dist[i], значит до j могу дойти за dist[i] + w. Оставляем меньшее из двух — записанного и нового.

Сколько нужно проходов

Одного мало: строки лежат как попало, и ребро может встретиться раньше, чем станет известен его старт. Путь без повторов содержит не больше 999 рёбер, поэтому тысячи проходов хватает всегда.

Тысяча проходов по двумстам рёбрам — доли секунды.

Прогон руками по графу из условия

Рёбра берём в том порядке, в каком они лежат в файле.

ребро	рассуждение	рекорды после шага
100 → 12	рекорд сотни пока бесконечность, ничего не меняется	1: 0
6 → 7	рекорд шестёрки бесконечность, снова мимо	1: 0
6 → 1	мимо	1: 0
1 → 7	0 + 5.5 меньше бесконечности — записываем	1: 0, 7: 5.5
7 → 100	5.5 + 2.0, записываем	1: 0, 7: 5.5, 100: 7.5
4 → 100	рекорд четвёрки бесконечность, мимо	без изменений
1 → 100	0 + 12.0 хуже рекорда 7.5, оставляем 7.5	без изменений
1 → 4	0 + 2.5, записываем	…, 4: 2.5

До вершины 12 рекорд не дошёл: когда смотрели ребро 100 → 12, у сотни ещё была бесконечность.

Что изменится на втором проходе?

Сработает только первое ребро: 100 → 12 даст 7.5 + 1.0 = 8.5. Остальные рекорды уже лучшие, и дальше ничего не меняется.

Итог: dist[100] = 7.5, ответ 7.

Тот же прогон по шагам

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

◀◀◀◀◀◀◀◀◀◀▶▶▶▶▶▶▶▶▶▶▶ показать всё▮▮ стопшаг 1 из 8 · стартшаг 2 из 8 · 100→12шаг 3 из 8 · 1→7шаг 4 из 8 · 7→100шаг 5 из 8 · 1→100шаг 6 из 8 · 1→4шаг 7 из 8 · 2-й проходшаг 8 из 8 · стопидёт показ…

До вершины 6 рекорда не появится никогда: в неё не ведёт ни одна стрелка.

Сначала про бесконечность

Вся программа держится на том, как ведёт себя float('inf'). Проверим руками.

INF = float('inf')

print(INF + 5.5)                             # прибавление ничего не меняет
print(INF > 1000000)                         # больше любого числа
print(min(INF, 7.5))                         # значит, min всегда выберет реальный путь
print(min(INF, INF + 2.0))                   # а из двух бесконечностей выйдет она же

BIG = 10 ** 9                                # а теперь заглушка вместо бесконечности
print(min(BIG, BIG + 2.0))                   # с положительным весом обошлось
print(min(BIG, BIG - 4.0))                   # а с отрицательным появился путь из ниоткуда
print(min(INF, INF - 4.0))                   # бесконечность так не обмануть

Результат работы программы

inf
True
7.5
inf
1000000000
999999996.0
inf

Бесконечность плюс вес остаётся бесконечностью — при любом знаке веса. Поэтому проверка «а добрались ли мы до начала ребра» не нужна вовсе.

Заглушка 10**9 ведёт себя иначе. С положительным весом она ещё держится, а на отрицательном ребре превращается в путь длиной 999999996 до вершины, куда дороги нет. В задаче про самый длинный путь она ломается сразу.

Алгоритм Форда-Беллмана. Реализация

Программа, которая считает кратчайший путь из вершины 1 в вершину 100.

Описание некоторых строк

строка	что делает
`dist = [INF] * 1001`	рекорды всех вершин, номер вершины — это индекс
`dist[1] = 0`	до стартовой вершины идти ноль
`for step in range(1000)`	проходов с запасом: путь короче 1000 рёбер
`for i, j, w in data`	берём рёбра по очереди, как они лежат в файле
`dist[i] + w`	сколько выйдет, если дойти до `i` и шагнуть по ребру
`min(dist[j], ...)`	оставляем лучшее из записанного и нового
`int(dist[100] + 0.000001)`	целая часть с запасом на погрешность

data = []
for s in open("graph.txt"):
    v1, v2, w = s.split()                    # split() режет по любым пробелам и табуляциям
    data.append((int(v1), int(v2), float(w)))

INF = float('inf')
dist = [INF] * 1001                          # dist[v] - рекорд: кратчайший путь из 1 в v
dist[1] = 0                                  # до самой единицы идти не надо

for step in range(1000):                     # вершин не больше 1000, проходов хватит
    for i, j, w in data:
        dist[j] = min(dist[j], dist[i] + w)

print(dist[100])
print(int(dist[100] + 0.000001))

Что печатает программа

30.799999999999997
30

Напечаталось 30.799999999999997, а не 30.8: из-за особенности хранения вещественных чисел в памяти компьютера.

Поэтому перед взятием целой части прибавляется крошечное число. Без него путь длиной ровно 31.0 мог бы накопиться как 30.999999999, и int() выдал бы 30 вместо 31.

Сначала печатай длину, потом целую часть.

Другой пример

Возьмём граф

Кратчайшее расстояние от 1 до 100 равно 31. Посмотрите ниже, что выдает код.

# для простоты зададим граф текстом
text = """1 2 4.1
2 3 12.2
3 100 14.7"""
 
data = []
for s in text.splitlines():
    v1, v2, w = s.split()
    data.append((int(v1), int(v2), float(w)))
INF = float('inf')
dist = [INF] * 1001
dist[1] = 0
for step in range(1000):
    for i, j, w in data:
        dist[j] = min(dist[j], dist[i] + w)
print(dist[100])                    # 30.999999999999996
print(int(dist[100]))               # 30  <- неправильно
print(int(dist[100] + 0.000001))    # 31  <- правильно

Ловушки

Взяли 10**9 вместо float('inf'). На этой задаче сойдёт, но привычка опасная.
Сделали один проход вместо тысячи. Строки в файле не отсортированы.
Написали dist[j] = dist[i] + w без min. Запишется последнее ребро, а не лучшее.
Взяли int() без запаса и потеряли единицу на ровном месте.
Завели массив на 101 ячейку и получили выход за границы.

Проверь себя

Расставьте шаги программы в том порядке, в каком они выполняются.

Проверить ответ

Граф из условия: какими станут рекорды после второго прохода по списку рёбер?

Проверить ответ

Файл graph.txt: целая часть длины кратчайшего пути из вершины 1 в вершину 502.

Проверить ответ

Attached files
graph.txt

Печать