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

Ключевые слова и синонимы: кратчайший путь; самый быстрый путь

Постановка задачи

Пусть дана сеть коммуникаций или дорожная сеть. Одна из наиболее естественных алгоритмических задач заключается в том, чтобы найти кратчайший путь из одной точки в другую. Задача нахождения кратчайшего пути между всеми парами вершин для ориентированного графа [math]\displaystyle{ G = (V, E, \ell \, ) }[/math] состоит в определении расстояния и кратчайшего пути между каждыми двумя вершинами, где [math]\displaystyle{ \mid V \mid = n, \mid E \mid = m, \ell : E \to \; \mathbb{R} }[/math] – функция длины дуги (или веса). На выходе мы получаем две матрицы формата n × n: D(u, v) – матрица расстояний от u до v , а S(u, v) = w, если (u, w) является первой дугой на кратчайшем пути из u в v. Задаче поиска кратчайшего пути между всеми парами нередко противопоставляются двухточечная задача кратчайшего пути и задача кратчайшего пути с единственным источником. Первая из них стремится найти кратчайший путь от заданной начальной вершины до заданной целевой вершины, вторая ищет все кратчайшие пути для заданной начальной вершины.

Определение расстояния Если функция ℓ присваивает только неотрицательные длины дуг, то определение расстояния представляется очевидным: D(u, v) – это путь минимальной длины из u в v, где длина пути равна общей длине составляющих его дуг. Однако в случае, если ℓ может присваивать отрицательные значения длин, могут существовать несколько осмысленных нотаций расстояния, зависящих от того, как обрабатываются контуры отрицательной длины. Предположим, что контур C имеет отрицательную длину, и что существуют такие [math]\displaystyle{ u, v \in V \, }[/math], что C достижим из u, а v достижима из C. Поскольку при перемещении из u в v контур C может быть пройден произвольное количество раз, не существует кратчайшего пути из u в v с конечным числом дуг. В некоторых случаях априори предполагается, что G не содержит контуров отрицательной длины; однако более разумно будет определить [math]\displaystyle{ D(u, v) = – \infty \, }[/math] в случае, если не существует конечного кратчайшего пути. Если определить D(u, v) как длину кратчайшего простого пути (без повторяющихся вершин), задача становится NP-полной. (Если все дуги имеют длину –1, тогда D(u, v) = – (n – 1) в том и только том случае, если G содержит Гамильтонов путь [7] из u в v). Можно также определить расстояние как длину кратчайшего пути, не содержащего повторяющихся вершин.

Классические алгоритмы

Алгоритм Беллмана-Форда решает задачу нахождения кратчайшего пути с единственным источником за время O(mn) в предположении, что длины дуг неотрицательны; алгоритм Дейкстры решает ее за время O(m + nlog n). Существует широко известное преобразование с сохранением кратчайших путей и временем выполнения O(mn), заменяющее любую функцию длины на неотрицательную функцию длины. Используя это преобразование и n проходов алгоритма Дейкстры, получаем алгоритм нахождения кратчайшего пути между всеми парами с временем выполнения [math]\displaystyle{ O(mn + n^2 log \; n) = O(n^3) }[/math]. Алгоритм Флойда-Уоршелла вычисляет кратчайший путь между всеми парами более прямолинейным способом и за время [math]\displaystyle{ O(n^3) }[/math]. Описание этих алгоритмов можно найти в [4]. Известно, что поиск кратчайшего пути между всеми парами является асимптотически эквивалентным матричному умножению (min; +) [1], которое поддается вычислению при помощи неравномерного алгоритма, выполняющего [math]\displaystyle{ O(n^{2.5}) }[/math] числовых операций [6]. (Наиболее быстрый известный матричный умножитель (min; +) выполняется за время [math]\displaystyle{ O(n^3(log \; log \; n)^3/(log \; n)^2) }[/math] [3]).

Графы с целочисленными весами

Наиболее современные исследования проблемы кратчайших путей предполагают, что длины дуг являются целыми числами в диапазоне {–C, ..., C} либо {0, ..., C}. Одно из направлений сводит поиск кратчайшего пути между всеми парами к серии стандартных операций матричного умножения. Применимость этих алгоритмов ограничена, поскольку время выполнения линейно растет пропорционально C. Существуют более быстрые алгоритмы для поиска кратчайшего пути с единственным источником как для неотрицательных длин дуг, так и для произвольных длин дуг. Первые задействуют мощь оперативной памяти, проводя сортировку за время o(n log n); вторые основываются на технике масштабирования. Цвик [19] приводит обзор алгоритмов нахождения кратчайших путей вплоть до 2001 года.

Основные результаты

Алгоритм Петти для поиска кратчайших путей между всеми парами [13] адаптирует иерархический подход Торупа [17] (разработанный для неориентированных графов с целочисленными весами) для ориентированных графов с действительными весами. Теорема 1 описывает первое улучшение времени выполнения по сравнению с [math]\displaystyle{ O(mn + n^2 log n) }[/math] алгоритма Дейкстры для произвольных графов с действительными весами.

Теорема 1. Пусть имеется ориентированный граф с действительными весами. Кратчайшие пути между всеми парами могут быть найдены за время [math]\displaystyle{ O(mn + n^2 loglog n) }[/math]. Этот алгоритм достигает логарифмического ускорения благодаря применению трех новых техник. Первая заключается в использовании неизбежного сходства между кратчайшими путями с единственным источником, исходящими из расположенных неподалеку вершин. Вторая представляет собой метод вычисления дискретных приближенных расстояний в графах с действительными весами. Третьей техникой является новый алгоритм иерархического типа для нахождения кратчайших путей с единственным источником, который при наличии приближенных расстояний достаточной точности выполняется за время O(m + n log log n).

Теорему 1 следует сравнивать с временными границами для других алгоритмов иерархического типа для поиска кратчайших путей между всеми парами [17,12,15].

Теорема 2 ([15], 2005). Пусть имеется неориентированный граф с действительными весами. Кратчайшие пути между всеми парами могут быть найдены за время O(mn log α(m, n)).

Теорема 3 ([17], 1999). Пусть имеется неориентированный граф G(V, E, ℓ), где функция ℓ назначает дугам целочисленные веса в диапазоне {[math]\displaystyle{ -2^{w-1}, ..., 2^{w-1} - 1 \, }[/math]}. Кратчайшие пути между всеми парами могут быть найдены за время O(mn) при использовании оперативной памяти с длиной слова w бит.

Теорема 4 ([14], 2002). Пусть имеется ориентированный граф с действительными весами. Кратчайшие пути между всеми парами могут быть найдены за полиномиальное время при помощи алгоритма, выполняющего O(mn log α(m, n)) числовых операций, где α – обратная функция Аккермана.

Второй результат исследований [13, 15] гласит, что не существует алгоритма иерархического типа для поиска кратчайших путей, время выполнения которого было бы лучше, чем O(m + n log n)алгоритма Дейкстры.

Теорема 5. Пусть G – входной граф, такой, что отношение максимальной длины дуги к минимальной равно r. Любой алгоритм поиска кратчайших путей для единственного источника иерархического типа выполняет Ω{m + min{n log n, n log r}) числовых операций, если граф G является ориентированным, и Ω(m + min{n log n, n log log r}) операций в противном случае.

Применение

Задача поиска кратчайших путей встречается в самых разных задачах оптимизации графов; среди них – совершенное паросочетание с минимальным весом, поток минимальной стоимости и циклы минимального среднего веса. Хорошо известным коммерческим приложением алгоритмов нахождения кратчайших путей является поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps.

Открытые вопросы

Дольше всего остаются нерешенными задачи улучшения времени алгоритмов Дейкстры и Беллмана-Форда для поиска кратчайших путей с единственным источником в графах с действительными весами.

Проблема 1. Существует ли алгоритм поиска кратчайших путей с единственным источником или двухточечный алгоритм для произвольных взвешенных графов с временем o(mn)?

Проблема 2. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с неотрицательными весами с временем выполнения O(m) + o(n log n)? Существует ли он для неориентированных графов?

Частичное решение проблемы 2 (для неориентированных графов) приведено в [15]. Возможно, самая удивительная из открытых проблем заключается в том, существует ли (асимптотическая) разность между сложностью алгоритма поиска кратчайших путей между всеми парами, алгоритма поиска кратчайших путей с единственным источником и двухточечного алгоритма поиска кратчайших путей на произвольных взвешенных графах.

Проблема 3. Является ли двухточечный алгоритм поиска кратчайших путей более простым, чем алгоритм поиска кратчайших путей между всеми парами, на произвольных взвешенных графах?

Проблема 4. Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической, т.е. меньше [math]\displaystyle{ O(n^{3 - \epsilon}) \, }[/math]?Существует ли алгоритм поиска кратчайших путей между всеми парами со сложностью ниже кубической для графов с целочисленными весами со слабой зависимостью от наибольшего веса дуги C, т. е. выполняющийся за время [math]\displaystyle{ O(n^{3 - \epsilon} polylog(C)) \, }[/math]?

Экспериментальные результаты

В [9, 16, 5] приведены результаты недавних экспериментов над алгоритмами поиска кратчайших путей с единственным источником. На разреженных графах лучшие алгоритмы поиска кратчайших путей между всеми парами используют неоднократные прогоны алгоритма кратчайших путей с единственным источником (возможно, с некоторыми предварительными вычислениями) [16]. На насыщенных графах наиболее важным аспектом вычислений становится эффективность использования кэша. В [18] приводится реализация алгоритма Флойда-Уоршелла с учетом эффективности кэша. Наиболее часто в последнее время используется подход с построением структур данных на основе линейных пространств, способных быстро давать точные или приближенные ответы на запрос кратчайших двухточечных путей; подробнее см. в [10, 6, 2, 11].

Наборы данных

См. в [5] данные о дорожных сетях США и Европы.

Ссылка на код

См. [8] и [5].

См. также

• Алгоритм поиска кратчайших путей при помощи матричного произведения
• Алгоритм поиска кратчайших путей с единственным источником

Литература

1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison-Wesley, Reading (1975)

2. Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest-path queries in road networks. In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007

3. Chan, T.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc. 39th ACM Symposium on Theory of Computing (STOC), 2007, pp. 590-598

4. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)

5. Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS Implementation challenge - shortest paths. http://www.dis.uniroma1.it/~challenge9/(2006)

6. Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1), 83-89 (1976)

7. Garey, M.R., Johnson, D.S.: Computers and Intractability: a guide to NP-Completeness. Freeman, San Francisco (1979)

8. Goldberg, A.V.: AVG Lab. http://www.avglab.com/andrew/

9. Goldberg, A.V.: Shortest path algorithms: Engineering aspects. In: Proc. 12th Int'l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2223, pp. 502-513. Springer, Berlin (2001)

10. Goldberg, A.V., Kaplan, H., Werneck, R.: Reach for A*: efficient point-to-point shortest path algorithms. In: Proc. 8th Workshop on Algorithm Engineering and Experiments (ALENEX), 2006

11. Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007

12. Pettie, S.: On the comparison-addition complexity of all-pairs shortest paths. In: Proc. 13th Int'l Symp. on Algorithms and Computation (ISAAC), 2002, pp. 32-43

13. Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs.Theor. Comput. Sci. 312(1), 47-74 (2004)

14. Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp. 713-722

15. Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398-1431 (2005)

16. Pettie, S., Ramachandran, V., Sridhar, S.: Experimental evaluation of a new shortest path algorithm. In: Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp. 126-142

17. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362-394 (1999)

18. Venkataraman, G., Sahni,S., Mukhopadhyaya, S.: A blocked all-pairs shortest paths algorithm. J. Exp. Algorithms 8 (2003)

19. Zwick, U.: Exact and approximate distances in graphs - a survey. In: Proc. 9th European Symposium on Algorithms (ESA), 2001, pp. 33-48. See updated version at http://www.cs.tau.ac.il/~zwick/