3.2.2 — кратчайшие пути между всеми парами вершин сразу3.2.2 — shortest paths between every pair of vertices at once
Иногда нужен не один кратчайший путь от старта, а полная матрица расстояний между всеми парами вершин. Запускать Дейкстру V раз — рабочий вариант, но для плотных графов есть более простой в реализации Флойд-Уоршелл, а для разреженных графов с отрицательными весами — более быстрый алгоритм Джонсона, комбинирующий Беллмана-Форда и Дейкстру из 3.2.1.Sometimes what's needed isn't one shortest path from a source, but the full distance matrix between every pair of vertices. Running Dijkstra V times works, but for dense graphs there's a simpler-to-implement Floyd-Warshall, and for sparse graphs with negative weights, a faster Johnson's algorithm combining Bellman-Ford and Dijkstra from 3.2.1.
Идея — динамическое программирование по "промежуточным вершинам": dist[k][i][j] — кратчайшее расстояние от i до j, используя в качестве промежуточных только вершины из {0, ..., k}. Переход: либо путь не использует вершину k вообще (dist[k-1][i][j]), либо использует (dist[k-1][i][k] + dist[k-1][k][j]) — берём минимум. Третье измерение k можно "сжать", обновляя матрицу на месте, потому что на шаге k используются только значения с меньшим или равным k, уже вычисленные корректно.The idea is dynamic programming over "intermediate vertices": dist[k][i][j] is the shortest distance from i to j using only vertices from {0, ..., k} as intermediates. The transition: either the path doesn't use vertex k at all (dist[k-1][i][j]), or it does (dist[k-1][i][k] + dist[k-1][k][j]) — take the minimum. The third dimension k can be "collapsed," updating the matrix in place, because step k only uses values with index ≤ k, already computed correctly.
разрешить ли пути через k — единственное решение на каждом шаге тройного циклаwhether to route through k — the single decision at each step of the triple loop
// dist[i][j] изначально: 0 если i==j, вес ребра если есть, INF иначе// dist[i][j] initially: 0 if i==j, edge weight if present, INF otherwise
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dist[i][k] < INF && dist[k][j] < INF)
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);Сложность O(V³) не зависит от числа рёбер — это одновременно и сила (тривиальная реализация, естественная работа с отрицательными весами без отрицательных циклов), и слабость (на разреженном графе с миллионом вершин V³ невозможно посчитать, тогда как V запусков Дейкстры дают O(VE log V), кардинально меньше при малом E).The O(V³) complexity doesn't depend on the number of edges — that's both a strength (trivial to implement, naturally handles negative weights with no negative cycles) and a weakness (on a sparse graph with a million vertices, V³ is infeasible to compute, whereas V runs of Dijkstra give O(VE log V), dramatically smaller when E is small).
Для разреженного графа с отрицательными весами: запускать Дейкстру V раз напрямую нельзя (отрицательные веса ломают Дейкстру, см. 3.2.1), а Флойд-Уоршелл — избыточно медленный при малом E. Джонсон решает это перевзвешиванием (reweighting): добавляет фиктивную вершину q с рёбрами веса 0 во все остальные, запускает от неё Беллмана-Форда один раз, получая потенциалы h(v) = dist(q, v), и пересчитывает вес каждого ребра как w'(u,v) = w(u,v) + h(u) - h(v). Математический факт, на котором это держится: новые веса всегда неотрицательны, а относительный порядок путей (какой из них короче) не меняется — потому что h(u) - h(v) телескопически сокращается на любом пути от u до v, оставляя лишь h(старт) - h(конец), одинаковую добавку для всех путей между одной парой вершин.For a sparse graph with negative weights: running Dijkstra V times directly is impossible (negative weights break Dijkstra, see 3.2.1), while Floyd-Warshall is needlessly slow when E is small. Johnson's algorithm fixes this via reweighting: it adds a dummy vertex q with zero-weight edges to every other vertex, runs Bellman-Ford from it once to get potentials h(v) = dist(q, v), and recomputes every edge's weight as w'(u,v) = w(u,v) + h(u) - h(v). The mathematical fact this rests on: the new weights are always non-negative, and the relative order of paths (which one is shorter) doesn't change — because h(u) - h(v) telescopes away along any path from u to v, leaving only h(start) - h(end), the same addition for every path between one pair of vertices.
После перевзвешивания граф безопасен для Дейкстры — запускаем её V раз (по разу от каждой вершины) на новых весах, затем "отменяем" перевзвешивание в полученных расстояниях. Итоговая сложность O(VE log V + VE) — для разреженного графа (E ≈ V) это O(V² log V), драматически быстрее O(V³) Флойда-Уоршелла на больших V.After reweighting, the graph is safe for Dijkstra — run it V times (once per vertex) on the new weights, then "undo" the reweighting in the resulting distances. The final complexity is O(VE log V + VE) — for a sparse graph (E ≈ V), that's O(V² log V), dramatically faster than Floyd-Warshall's O(V³) for large V.
Атлас или логистическая система с фиксированным небольшим числом узлов (сотни городов, а не миллионы перекрёстков) — идеальный случай для предвычисления полной матрицы расстояний один раз офлайн и последующих O(1) запросов "расстояние от A до B" в рантайме.An atlas or a logistics system with a small fixed number of nodes (hundreds of cities, not millions of intersections) — an ideal case for precomputing the full distance matrix once offline, then O(1) "distance from A to B" lookups at runtime.
Замена операции "сложение весов, минимум" на "логическое И, логическое ИЛИ" превращает Флойда-Уоршелла в алгоритм проверки достижимости между всеми парами вершин сразу — используется в базах данных при вычислении транзитивного замыкания отношений (например, "все предки узла в иерархии").Swapping the "sum weights, take minimum" operation for "logical AND, logical OR" turns Floyd-Warshall into an algorithm checking reachability between every pair of vertices at once — used in databases when computing the transitive closure of a relation (e.g., "all ancestors of a node in a hierarchy").
Некоторые авиакомпании эффективно субсидируют определённые маршруты (стыковка дешевле прямого перелёта из-за программ лояльности/налоговых льгот) — граф маршрутов с такими "отрицательными" весами, разреженный (не все пары городов соединены напрямую), — ровно случай, где Джонсон выигрывает у Флойда-Уоршелла.Some airlines effectively subsidize certain routes (a connection is cheaper than a direct flight due to loyalty programs/tax breaks) — a route graph with such "negative" weights, sparse (not every city pair connects directly) — exactly the case where Johnson's algorithm beats Floyd-Warshall.
"Насколько влиятелен пользователь в сети" в некоторых метриках буквально требует знать кратчайшие пути между всеми парами пользователей (или их выборкой) — closeness centrality = обратное к сумме кратчайших расстояний от вершины до всех остальных."How influential is a user in the network" for some metrics literally requires knowing shortest paths between every pair of users (or a sample of them) — closeness centrality is the inverse of the sum of shortest distances from a vertex to all others.
Пошаговая стратегия с картой из сотен клеток может позволить себе предпосчитать все попарные расстояния один раз за ход, чтобы у каждого юнита ИИ был мгновенный доступ к "кратчайший путь до любой другой клетки" без повторного запуска Дейкстры на каждое решение.A turn-based strategy game with a map of a few hundred cells can afford to precompute all pairwise distances once per turn, so every AI unit gets instant access to "shortest path to any other cell" without rerunning Dijkstra for every decision.
Внешний цикл обязан быть по k (промежуточная вершина), а не по i или j — переставить их местами нарушает инвариант динамического программирования (на шаге k должны быть уже корректны все dist, использующие вершины ≤ k) и даёт неверные результаты без какой-либо ошибки компиляции или исключения.The outer loop must be over k (the intermediate vertex), not i or j — swapping the order breaks the DP invariant (at step k, every dist using vertices ≤ k must already be correct) and produces wrong results with no compile error or exception.
Как и Беллман-Форд, алгоритм требует отсутствия отрицательных циклов для корректности понятия "кратчайший путь". Признак наличия цикла — отрицательное значение на диагонали (dist[v][v] < 0) после завершения алгоритма — эту проверку часто забывают добавить.Like Bellman-Ford, the algorithm requires no negative cycles for "shortest path" to be well-defined. The tell is a negative value on the diagonal (dist[v][v] < 0) after the algorithm finishes — this check is often forgotten.
Флойд-Уоршелл проще для запоминания и написания на собеседовании, из-за чего его часто выбирают автоматически — но на графе с V=100 000 и разреженными связями O(V³) физически невозможно посчитать за разумное время, тогда как V запусков Дейкстры (или Джонсон при отрицательных весах) отработают на порядки быстрее.Floyd-Warshall is easier to remember and write in an interview, which makes it a common default choice — but on a graph with V=100,000 and sparse connections, O(V³) is physically infeasible to compute in reasonable time, whereas V runs of Dijkstra (or Johnson's algorithm under negative weights) finish orders of magnitude faster.