# конспект · шаг 6 из 6
Конспект: все пары кратчайших путей
Понятия
Флойд-Уоршелл - три вложенных цикла, k снаружи:
d[i][j] = min( d[i][j], d[i][k] + d[k][j] )
после k-й итерации: кратчайший путь через промежуточные вершины с номерами ≤ k
Потенциалы (Джонсон) - h[v] = расстояние от фиктивной вершины; перевзвешивание
w'(u,v) = w(u,v) + h[u] − h[v].
Полукольцо операций - «склеить вдоль пути» и «выбрать лучший путь»; замена пары даёт другую задачу тем же кодом.
Что унести
| задача | ЛУЧШЕЕ | СКЛЕИТЬ | диагональ |
|---|---|---|---|
| кратчайшие пути | min |
+ |
0 |
| транзитивное замыкание (Уоршелл) | ИЛИ | И | истина |
| максимальная пропускная способность | max |
min |
+∞ |
| самый надёжный путь | max |
× |
1 |
Выбор алгоритма:
| случай | алгоритм | цена |
|---|---|---|
плотный граф, небольшое V |
Флойд-Уоршелл | O(V³), память O(V²) |
| разреженный, неотрицательные веса | V Дейкстр |
O(V·E·log V) |
| разреженный, есть отрицательные | Джонсон | O(V·E·log V) + O(V·E) |
| нужна только достижимость | Уоршелл на битовых словах | O(V³), константа /64 |
k - это РАЗРЕШЕНИЕ, выдаваемое всей матрице, поэтому цикл по нему внешний;
i и j внутри независимы и переставляются свободно
Отрицательный цикл в Флойде виден как d[i][i] < 0. Маршруты восстанавливают матрицей nxt.
Джонсон: неотрицательность новых весов - из неравенства треугольника h[v] <= h[u] + w;
сохранение кратчайших путей - из телескопической суммы: длина ЛЮБОГО пути между парой меняется на
одну и ту же величину h[u] − h[v]. Фиктивная вершина нужна, чтобы все потенциалы были конечны, и
заодно ловит все отрицательные циклы графа.
Тихие ошибки: k не снаружи (ответ неверен молча); забытая нейтральная диагональ при смене
операций; INF + INF без защиты от переполнения; перепутанные знаки в перевзвешивании; забытый
обратный пересчёт d = d' − h[u] + h[v].
Куда это ведёт
Следующая глава - эвристический поиск: A* устроен на тех же потенциалах, только берутся они не из Беллмана-Форда, а из оценки «сколько осталось до цели».
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий