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

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