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

Кратчайший путь в графе - Флойд: все пути сразу

Второй инструмент

Форд–Беллман считает пути из одной вершины. Флойд–Уоршелл считает их сразу между всеми парами и складывает в таблицу.

Для базового вопроса это перебор мощности, но половина формулировок задания решается по такой таблице одной строкой. И заодно это второй независимый способ: два разных алгоритма обязаны дать одно число.

Идея: разрешаем пересадки по одной

Заводим квадратную таблицу: W[i][j] — кратчайший путь из i в j. Сначала в ней только сами рёбра, остальное бесконечность.

Дальше берём вершину k и разрешаем через неё ездить: если из i доехать до k, а потом из k до j дешевле, чем напрямую, — переписываем клетку.

Внешний цикл — по пересадкам, внутренние — по клеткам таблицы.

Перебрав так все вершины в роли k, получаем настоящие кратчайшие пути между всеми парами.

Почему порядок k не важен

После обработки очередной k в таблице лежат кратчайшие пути, которым разрешены пересадки в уже пройденных вершинах. Какая вершина окажется в этом наборе раньше, а какая позже, роли не играет — важно лишь, что каждая побывала снаружи ровно один раз.

Чего делать не нужно

Диагональ W[i][i] обнулять не обязательно: она участвует только там, где ничего не улучшает. И перенумеровывать вершины не нужно — таблица и так на 1001 строку.

Сложность

Три вложенных цикла по числу вершин. Двести рёбер могут дать до четырёхсот разных вершин, и тогда клеток набирается 64 миллиона.

вершин в файле	Форд–Беллман	Флойд
20	0.1 с	0.1 с
247	0.1 с	2.1 с
397	0.1 с	10.7 с

Замеры настоящие, на файлах ровно по 200 рёбер. Вывод простой: если нужен один путь — Форд–Беллман, если нужны все пары или путь через заданную вершину — Флойд, и десять секунд можно потерпеть.

Как таблица заполняется

Возьмём три вершины и одно разрешение на пересадку. Смотри, как клетка 1 → 100 меняется, когда мы разрешаем ходить через вершину 7.

INF = float('inf')
W = [[INF] * 101 for _ in range(101)]        # маленькая таблица для примера

W[1][7] = 5.5                                # знаем только два ребра
W[7][100] = 2.0

print(W[1][100])                             # прямого ребра нет - бесконечность
print(W[1][7] + W[7][100])                   # а через семёрку выходит 7.5

if W[1][7] + W[7][100] < W[1][100]:          # эта проверка и есть весь Флойд
    W[1][100] = W[1][7] + W[7][100]

print(W[1][100])                             # клетка заполнилась
print(W[100][1])                             # обратно пути нет, граф ориентированный

Что печатает демонстрация

inf
7.5
7.5
inf

Настоящий Флойд делает ровно это, только перебирает все вершины в роли пересадки и все пары клеток. Три вложенных цикла — и таблица заполнена целиком.

Что делает каждая строка основной программы

строка	что делает
`W = [[INF] * 1001 ...]`	таблица на все пары номеров, из условия L и M до 1000
`W[v1][v2] = w`	заносим сами рёбра, остальное пока бесконечность
`for k in vertices`	разрешаем пересадку в вершине k — этот цикл обязан быть внешним
`for i, for j`	проверяем все пары «откуда — куда»
`W[i][k] + W[k][j]`	доехать до пересадки, потом от неё
`W[1][100]`	готовый ответ достаётся из таблицы без нового запуска

INF = float('inf')
W = [[INF] * 1001 for _ in range(1001)]      # W[i][j] - кратчайший путь из i в j
vertices = set()

for s in open("graph.txt"):
    v1, v2, w = s.split()
    v1, v2, w = int(v1), int(v2), float(w)
    W[v1][v2] = w                            # сначала знаем только сами рёбра
    vertices.add(v1)
    vertices.add(v2)

for k in vertices:                           # разрешаем ходить через вершину k
    for i in vertices:
        for j in vertices:
            if W[i][k] + W[k][j] < W[i][j]:
                W[i][j] = W[i][k] + W[k][j]

print(W[1][100])                             # то же, что считал Форд-Беллман
print(W[66][100])                            # а это бесплатное дополнение
print(W[810][100])
print(int(W[1][100] + 0.000001))

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

30.799999999999997
11.399999999999999
47.4
30

Первое число совпало с ответом прошлой тетради — два независимых алгоритма сошлись, значит можно верить.

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

Ловушки

Перепутали порядок циклов. Вершина k обязана быть снаружи, иначе алгоритм неверен.
Гоняют циклы по range(1001) вместо множества вершин. Это миллиард пустых клеток и минуты ожидания.
Заполнили W[v1][v2] и заодно W[v2][v1]. Граф ориентированный, обратного ребра нет.
Забыли, что при кратных рёбрах клетка затрётся последним весом. В нашем задании такого не бывает — в условии обещано не больше одного ребра между парой вершин.

Проверь себя

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

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

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

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

Attached files
graph.txt

Печать