Поиск кратчайшего пути от одной вершины (SSSP)
Содержание
1 Постановка задачи
Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math] и выделенной вершиной-источником [math]u[/math]. Последовательность [math]P(u, v)[/math] рёбер [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] называется путём, идущим от вершины [math]u[/math] к вершине [math]v[/math]. Суммарный вес этого пути равен
- [math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]
Требуется для каждой вершины [math]v[/math], достижимой из вершины-источника [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:
- [math] f(P^*(u, v)) = \min f(P(u, v)). [/math]
2 Варианты задачи
Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.
В зависимости от ограничений на возможные значения весов различают следующие случаи.
- Единичные веса. В этом случае задача существенно упрощается и может быть решена за линейное время алгоритмом поиска вширь.
- Положительные целые веса. Задача также может быть решена за линейное время[1] (хотя и с большей константой).
- Неотрицательные веса. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
- Произвольные веса. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.
3 Свойства задачи
Решение задачи удовлетворяет принципу оптимальности: если путь [math]P^*(u, w)[/math] является частью кратчайшего пути [math]P^*(u, v)[/math], то [math]P^*(u, w)[/math] является кратчайшим путём от источника [math]u[/math] до вершины [math]w[/math].
Принцип оптимальности означает, что для каждой вершины [math]v[/math] вместо всего кратчайшего пути [math]P^*(u, v)[/math] достаточно хранить его последнее ребро [math]e^*_v[/math]. Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_w[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].
4 Описание входных и выходных данных
Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]), вершина-источник [math]u[/math].
Объём входных данных: [math]O(m + n)[/math].
Выходные данные: для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math].
Объём выходных данных: [math]O(n)[/math].
5 Алгоритмы решения задачи
- Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(m)[/math].
- Алгоритм Дейкстры для ориентированных графов с неотрицательными весами, сложность [math]O(m + n \ln n)[/math].[2][3]
- Алгоритм Беллмана-Форда для ориентированных графов с произвольными весами, сложность [math]O(mn)[/math].
- Алгоритм Δ-шагания для ориентированных графов с неотрицательными весами, средняя сложность [math]O(n + m + dL)[/math], параллельная сложность [math]O((dL + \ln n) \ln n[/math] со средней работой [math]O(n + m + dL \ln n)[/math].[4]
- Алгоритм Торупа для неориентированных графов с положительными целыми весами, сложность [math]O(m)[/math].[1]
Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальная длина кратчайшего пути.
6 Ссылки
- ↑ 1,0 1,1 Thorup, Mikkel. “Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time.” Journal of the ACM 46, no. 3 (May 1, 1999): 362–94. doi:10.1145/316542.316548.
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
- ↑ Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1, 1987): 596–615. doi:10.1145/28869.28874.
- ↑ Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.
