Поиск кратчайшего пути от одной вершины (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^*(v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]
Название задачи на английском языке – «Single Source Shortest Path» (SSSP).
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]O(m)[/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]w[/math];
- для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].
Объём выходных данных: [math]O(n)[/math].
4.1 Преобразование выходных данных и поиск кратчайшего пути
Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_w[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].
Рёбра [math]e^*_v[/math] могут быть восстановлены за время [math]O(m)[/math] перебором рёбер для каждой вершины:
- [math] e^*_v \in \{ (w, v) \in E \mid f^*(v) = f^*(w) + f((v, w)) \}. [/math]
Перебор может осуществляться параллельно.
Для поиска кратчайших расстояний [math]f^*(v)[/math] по набору рёбер [math]e^*_v[/math], необходимо построить из них дерево, на котором выполнить поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации).
5 Алгоритмы решения задачи
- Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(m)[/math].
- Алгоритм Дейкстры[2][3] для ориентированных графов с неотрицательными весами, сложность [math]O(m + n \ln n)[/math].
- Алгоритм Беллмана-Форда[4][5][6] для ориентированных графов с произвольными весами, сложность [math]O(mn)[/math].
- Алгоритм Δ-шагания[7] для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n + m + dL)[/math], параллельная сложность [math]O((dL + \ln n) \ln n[/math] со средней работой [math]O(n + m + dL \ln n)[/math].
- Алгоритм Торупа[1] представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(m)[/math].
- В ориентированном ациклическом графе с произвольными весами время поиска кратчайших путей линейное – [math]O(m + n)[/math], алгоритм основан на топологической сортировке графа.
Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.
Перечисленные алгоритмы могут использоваться и для решения задачи поиска кратчайшего пути для всех пар вершин графа (для этого необходимо запустить соответствующий алгоритм для каждой вершины графа, что при необходимости можно сделать параллельно), при этом оценка сложности умножается на [math]n[/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.
- ↑ Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
- ↑ Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
- ↑ Moore, Edward F. “The Shortest Path Through a Maze,” 285–92, 1959.
- ↑ 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.
