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

Ключевые слова и синонимы

Кратчайший путь; самый быстрый путь

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

Задача поиска кратчайших путей с единственным источником (single source shortest path problem, SSSP) выглядит следующим образом. Пусть имеется граф [math]\displaystyle{ G = (V, E, \ell) \; }[/math] и вершина-источник [math]\displaystyle{ s \in V \; }[/math]. Требуется найти кратчайший путь из вершины s в каждую вершину [math]\displaystyle{ v \in V \; }[/math]. Сложность задачи зависит от того, является ли граф ориентированным или нет, а также от предположений о функции длины [math]\displaystyle{ \ell \; }[/math]. В самом общем случае [math]\displaystyle{ \ell: E \to \mathbb{R} \; }[/math] присваивает ребрам произвольные (положительные и отрицательные) вещественные длины. В этой ситуации можно применить алгоритмы Беллмана-Форда и Эдмондса [1, 4], время выполнения которых составит примерно O(mn), где m = |E| и n = |V| – количества ребер и вершин. (Алгоритм Эдмондса работает на неориентированных графах и предполагает, что в них не имеется простых циклов отрицательной длины).

Если функция [math]\displaystyle{ \ell \; }[/math] присваивает ребрам только неотрицательные вещественные длины, то можно применить алгоритмы Дейкстры и Петти-Рамачандрана [4, 14] к ориентированным и неориентированным графам, соответственно. Эти алгоритмы имеют узкое место в виде сортировки и в наихудшем случае требуют [math]\displaystyle{ \Omega(m + n \; log \; n) }[/math] времени. (Алгоритм из [14] выполняется за время O(m + n log log n), если отношение длин любых двух ребер представляет собой полином от n).

В общем случае предполагается, что функция [math]\displaystyle{ \ell \; }[/math] присваивает ребрам целочисленные длины в диапазоне [math]\displaystyle{ \{ 0, ..., 2^w - 1 \} \; }[/math] или [math]\displaystyle{ \{ -2^{w - 1}, ..., 2^{w - 1} - 1 \} \; }[/math] и что компьютер имеет оперативную память со словами длины w; это означает, что каждая длина ребра помещается в одном регистре. Для ребер общего вида с целочисленной длиной лучшие SSSP-алгоритмы превосходят алгоритмы Беллмана-Форда и Эдмондса примерно в [math]\displaystyle{ \sqrt{n} \; }[/math] раз [7]. Для ребер с неотрицательной целочисленной длиной скорость лучших SSSP-алгоритмов превосходит скорость работы алгоритмов Дейкстры и Петти-Рамачандрана на логарифмический коэффициент. Эти алгоритмы нередко основываются на целочисленных очередях с приоритетами [10].

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

Главным результатом работы Торупа [17] стал оптимальный SSSP-алгоритм с линейным временем выполнения для неориентированных графов с целочисленными длинами ребер. Это первый и единственный алгоритм поиска кратчайших путей, не делающий серьезных предположений о классе входного графа.

Теорема 1. Существует SSSP-алгоритм для неориентированных графов с целочисленными весами ребер, выполняющийся за время O(m).

Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления иерархии компонентов за линейное время. Алгоритм из [17] действует подобно алгоритму Дейкстры [4], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [18] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей запятой. (Определение кратчайшего пути обладает определенной гибкостью, поскольку сложение с плавающей запятой не является ни коммутативным, ни ассоциативным)).

Основанный на иерархии подход Торупа был в дальнейшем распространен на ориентированные графы и/или графы с вещественными весами и в таком виде позволил решить задачу поиска кратчайших путей между всеми парами (all pairs shortest path, APSP) [12, 13, 14]. Обобщения до соответствующих SSSP-задач можно суммировать следующим образом. В работах [12, 13] можно найти более подробное изложение основанных на использовании иерархии APSP-алгоритмов.

Теорема 2 (Хагеруп [9], 2000). Иерархия компонентов для ориентированного графа [math]\displaystyle{ G = (V, E, \ell) \; }[/math], где [math]\displaystyle{ \ell: E \to \{ 0, ..., 2^w - 1 \} }[/math], может быть построена за время O(m log w). После этого поиск кратчайших путей из любого единственного источника может быть произведен за время O(m + n log log n).

Теорема 3 (Петти и Рамачандран [14], 2005). Иерархия компонентов для неориентированного графа [math]\displaystyle{ G = (V, E, \ell) \; }[/math], где [math]\displaystyle{ \ell: E \to \mathbb{R}^+ }[/math], может быть построена за время [math]\displaystyle{ O(m \alpha (m, n) + min \{ n \; log \; log \; r, n \; log \; n \}) }[/math], где r – отношение максимальной длины ребра к минимальной. Следовательно, поиск кратчайших путей из любого единственного источника может быть произведен за время [math]\displaystyle{ O(m \; log \; \alpha (m, n)) }[/math].

Алгоритмы Хагерупа [9] и Петти-Рамачандрана [14] применяют тот же базовый подход, что и алгоритм Торупа: некоторая разновидность иерархии компонентов используется для определения групп вершин, которые можно безопасно посещать в любом порядке. Однако в случае ориентированных графов [9] и действительных длин ребер [14] иерархия Торупа становится неприменимой или неэффективной. Иерархия компонентов Хагерупа основывается на ориентированном аналоге минимального остовного дерева. Алгоритм Петти-Рамачандрана формирует определенный баланс на базе иерархии компонентов, а затем при вычислении кратчайших путей с единственным источником использует специализированную очередь приоритетов, реализующую преимущества этого баланса.

Применение

Алгоритмы поиска кратчайших путей часто используются в качестве подпрограмм в других задачах оптимизации, таких как задачи о потоке и паросочетании [1] и определении местоположения [19]. Широко практикуется такое коммерческое применение алгоритмов нахождения кратчайших путей, как поиск эффективных маршрутов в дорожных сетях – к примеру, в Google Maps, MapQuest или Yahoo Maps.

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

Алгоритм Торупа для решения SSSP-задачи [17] выполняется за линейное время и потому является оптимальным. Основной задачей остается поиск SSSP-алгоритма с линейным временем выполнения, работающего на ориентированных графах с вещественными весами ребер. Наилучшее время выполнения для неориентированных графов с вещественными весами ребер приведено в теореме 3. Для ориентированных графов с целыми весами самые быстрые алгоритмы основаны на подходе Дейкстры (а не теореме 2) и выполняются за время [math]\displaystyle{ O(m \sqrt{log \; log \; n}) }[/math] (рандомизированные) и [math]\displaystyle{ O(m + n \; log \; log \; n) }[/math] (детерминированные).

Задача 1. Существует ли алгоритм поиска кратчайших путей с единственным источником для ориентированных графов с целыми весами с временем выполнения O(m)?

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

Также остается открытым вопрос о сложности SSSP-алгоритмов на графах с положительными и отрицательными длинами ребер.

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

Асано и Имаи [2], а также Петти и др. [15] оценили эффективность основанных на иерархии SSSP-алгоритмов [14, 17]. Исследования SSSP-алгоритмов на ориентированных графах с целочисленными весами производились неоднократно; наиболее актуальные сведения см. в работе [8] и ссылках в ней. В последнее время исследователи стремятся найти практичные схемы предварительной обработки, способные очень быстро давать ответы на запрос кратчайших двухточечных путей. Подробнее о недавних работах в этой области – в [3, 11, 16].

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

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

Ссылка на код

См. [6] и [5].

См. также

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

Литература

1. Ahuja, R.K., Magnati, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)

2. Asano, Y., Imai, H.: Practical efficiency of the linear-time algorithm for the single source shortest path problem. J. Oper. Res. Soc.Jpn.43(4),431-447 (2000)

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

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 Challege—Shortest Paths. http://www.dis.uniroma1.it/~challenge9/(2006)

6. Goldberg, A.V.: AVG Lab. http://www.avglab.com/andrew/7. Goldberg, A.V.: Scaling algorithms for the shortest paths problem. SIAM J. Comput. 24(3),494-504 (1995)

8. 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)

9. Hagerup, T.: Improved shortest paths on the word RAM. In: Proc. 27th Int'l Colloq. on Automata, Languages, and Programming (ICALP). LNCS vol. 1853, pp. 61-72. Springer, Berlin (2000)

10. Han, Y.,Thorup, M.: Integer sorting in O(nlog log n) expected time and linear space. In: Proc. 43rd Symp. on Foundations of Computer Science (FOCS), 2002, pp. 135-144

11. Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proceedings 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.: A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398-1431 (2005)

15. 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

16. Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Proc. 14th European Symposium on Algorithms (ESA), 2006, pp. 804-816

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

18. Thorup, M.: Floats, integers, and single source shortest paths. J. Algorithms 35 (2000)

19. Thorup, M.: Quick and good facility location. In: Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003, pp. 178-185