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

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

1 Алгоритм Эдмондса работает на неориентированных графах и предполагает, что в них не имеется простых циклов отрицательной длины.

2 Алгоритм из [14] выполняется за время O(m + n log log n), если отношение длин любых двух ребер представляет собой полином от n.

В общем случае предполагается, что I присваивает ребрам целочисленные длины в диапазоне {0, ... , 2w - 1} или {-2W~1, ... : : 2W~1 – 1}, и что компьютер имеет оперативную память со словами длины w; это означает, что каждая длина ребра помещается в одном регистре. Для ребер общего вида с целочисленной длиной лучшие SSSP-алгоритмы превосходят алгоритмы Беллмана-Форда и Эдмондса примерно в pn раз [7]. Для ребер с неотрицательной целочисленной длиной скорость лучших SSSP-алгоритмов превосходит скорость работы алгоритмов Дейкстры и Петти-Рамачандрана на логарифмический коэффициент. Эти алгоритмы нередко основываются на целочисленных очередях с приоритетами [10].