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

Перейти к навигации Перейти к поиску
Строка 11: Строка 11:


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




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




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


3 Определение кратчайшего пути обладает определенной гибкостью, поскольку сложение с плавающей точкой не является ни коммутативным, ни ассоциативным.


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


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


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


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


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


Теорема 3 (Петти и Рамачандран [14], 2005). Иерархия компонентов для неориентированного графа G = (V, E, l), где 1: E ! R+, может быть построена за время O(ma(m, n)+minfnloglogr; nlog ng), где r – отношение максимальной длины ребра к минимальной. Следовательно, поиск кратчайших путей из любого единственного источника может быть произведен за время O(m log a(m, n)).


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


== Применение ==
== Применение ==
4551

правка

Навигация