4551
правка
Алгоритм поиска кратчайших путей с единственным источником: различия между версиями
Материал из WEGA
Алгоритм поиска кратчайших путей с единственным источником (посмотреть исходный код)
Версия от 22:43, 6 февраля 2018
, 6 февраля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
== Основные результаты == | == Основные результаты == | ||
Главным результатом работы Торупа [ ] стал оптимальный SSSP-алгоритм с линейным временем выполнения для неориентированных графов с целочисленными длинами ребер. Это первый и единственный алгоритм поиска кратчайших путей, не делающий серьезных предположений о классе входного графа. | Главным результатом работы Торупа [17] стал оптимальный SSSP-алгоритм с линейным временем выполнения для неориентированных графов с целочисленными длинами ребер. Это первый и единственный алгоритм поиска кратчайших путей, не делающий серьезных предположений о классе входного графа. | ||
Теорема 1. Существует SSSP-алгоритм для неориентированных графов с целочисленными весами ребер, выполняющийся за время O(m). | '''Теорема 1. Существует SSSP-алгоритм для неориентированных графов с целочисленными весами ребер, выполняющийся за время O(m).''' | ||
Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления иерархии компонентов за линейное время. Алгоритм из [ ] действует подобно алгоритму Дейкстры [ ], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [ ] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей точкой. | Торупу удалось избежать «бутылочного горлышка» сортировки, присущего алгоритму Дейкстры, за счет предварительного вычисления ''иерархии компонентов'' за линейное время. Алгоритм из [17] действует подобно алгоритму Дейкстры [4], но использует иерархию компонентов для определения групп вершин, которые могут быть посещены в любом порядке. В более поздней работе [18] Торуп расширил алгоритм таким образом, чтобы он мог работать с длинами ребер, представляющими собой числа с плавающей точкой. (''Определение кратчайшего пути обладает определенной гибкостью, поскольку сложение с плавающей точкой не является ни коммутативным, ни ассоциативным'')). | ||
Основанный на иерархии подход Торупа был в дальнейшем распространен на ориентированные графы и/или графы с вещественными весами и в таком виде позволил решить задачу ''поиска кратчайших путей между всеми парами'' (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).''' | |||
'''Теорема 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>.''' | |||
Алгоритмы Хагерупа [9] и Петти-Рамачандрана [14] применяют тот же базовый подход, что и алгоритм Торупа: некоторая разновидность иерархии компонентов используется для определения групп вершин, которые можно безопасно посещать в любом порядке. Однако в случае ориентированных графов [9] и действительных длин ребер [14] иерархия Торупа становится неприменимой или неэффективной. Иерархия компонентов Хагерупа основывается на ориентированном аналоге [[Минимальное остовное дерево|минимального остовного дерева]]. Алгоритм Петти-Рамачандрана формирует определенный баланс на базе иерархии компонентов, а затем при вычислении кратчайших путей с единственным источником использует специализированную очередь приоритетов, реализующую преимущества этого баланса. | |||
Алгоритмы Хагерупа [ ] и Петти-Рамачандрана [14] применяют тот же базовый подход, что и алгоритм Торупа: некоторая разновидность иерархии компонентов используется для определения групп вершин, которые можно безопасно посещать в любом порядке. Однако в случае ориентированных графов [9] и действительных длин ребер [14] иерархия Торупа становится неприменимой или неэффективной. Иерархия компонентов Хагерупа основывается на ориентированном аналоге минимального остовного дерева. Алгоритм Петти-Рамачандрана формирует определенный баланс на базе иерархии компонентов, а затем при вычислении кратчайших путей с единственным источником использует специализированную очередь приоритетов, реализующую преимущества этого баланса. | |||
== Применение == | == Применение == | ||
