Какой самый быстрый алгоритм поиска всех кратчайших путей в разреженном графе?

В невзвешенном неориентированном графе с вершинами и ребрами, такими, что , каков самый быстрый способ найти все кратчайшие пути в графе? Можно ли сделать это быстрее, чем Флойд-Варшалл, который является но очень быстро за итерацию?E 2 V > E O ( V 3$V$$E$$2V \gt E$$O(V^3)$

Как насчет того, если график взвешен?

Поскольку это невзвешенный граф, вы можете запустить поиск в ширину (BFS) по каждой вершине в графе. Каждый прогон BFS дает вам кратчайшие расстояния (и пути) от начальной вершины до любой другой вершины. Временная сложность для одной BFS равна так как в вашем разреженном графе. Запуск его раз дает вам время сложность.O ( V + E ) = O ( V ) E = O ( V ) V O ( V 2$v$$O(V + E) = O(V)$$E = O(V)$$V$$O(V^2)$

Для взвешенного ориентированного графа алгоритм Джонсона, предложенный Ювалом, является самым быстрым для разреженных графов. Требуется которое в вашем случае оказывается . Для взвешенного неориентированного графа вы можете либо запустить алгоритм Дейкстры из каждого узла, либо заменить каждое неориентированное ребро двумя противоположно направленными ребрами и запустить алгоритм Джонсона. И то и другое даст то же самое асимптотическое время, что и алгоритм Джонсона выше для вашего разреженного случая. Также обратите внимание, что упомянутый выше подход BFS работает как для ориентированных, так и для неориентированных графов.O ( V 2 log V $O(V^2\log V + VE)$$O(V^2\log V)$

Есть алгоритм Джонсона , время работы которого равно .$O(V^2\log V + VE)$

Вы можете попробовать сделать версию Floyd-Warshall более быстрой на разреженных матрицах.

Во-первых, давайте вспомним, что делает этот алгоритм:

Пусть - матрица расстояний. В начале алгоритма - вес ребра . Если это ребро не существует, то .M i , j i → j M i , j = $M$$M_{i,j}$$i \rightarrow j$$M_{i,j}=\infty$

Алгоритм имеет шагов. На шаге алгоритма для каждой пары узлов мы устанавливаемk i , $V$$k$$i,j$

$$M_{i,j} \leftarrow \min\{M_{i,j}, M_{i,k}+M_{k,j}\}.$$

Ясно, что если или обновление не требуется. Таким образом, на первых этапах алгоритма нам нужно только приблизительно выполнить где и обозначают количество входящих и исходящих ребер узла соответственно. По мере развития алгоритма заполняется все больше и больше элементов матрицыСледовательно, последние шаги могут занять гораздо больше времени.$M_{i,k}=\infty$$M_{k,j}=\infty$$deg_{in}(k) \cdot deg_{out}(k)$$deg_{in}(k)$$deg_{out}(k)$$k$$M$

Обратите внимание, что нам нужен эффективный способ итерации только по бесконечным ячейкам в строке и столбце матрицы. Это можно сделать, сохранив набор входящих и исходящих ребер для каждого узла.$k$

Похоже, что первые шаги алгоритма могут значительно выиграть от разреженности. Например, случайно построенный граф с предполагает, что первая итерация ( ) состоит всего из шагов. Если график разбит на множество связанных компонентов, то матрица будет оставаться относительно разреженной по всему алгоритму, а общее время выполнения может составлять всего . С другой стороны, если граф содержит только одну связную компоненту, то последняя итерациякак ожидается, предпримет шагов. В этом случае общее время выполнения может быть . Столь же, как не разреженная версия.k = 0 O ( 1 ) M O ( V ) k = | V | O ( V 2 ) O ( V 3$E=O(V)$$k=0$$O(1)$$M$$O(V)$$k=|V|$$O(V^2)$$O(V^3)$