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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 45: Строка 45:
 
* [[Алгоритм Дейкстры]] для ориентированных графов с неотрицательными весами, сложность <math>O(m + n \ln n)</math>.<ref>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.</ref><ref>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.</ref>
 
* [[Алгоритм Дейкстры]] для ориентированных графов с неотрицательными весами, сложность <math>O(m + n \ln n)</math>.<ref>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.</ref><ref>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.</ref>
 
* [[Алгоритм Беллмана-Форда]] для ориентированных графов с произвольными весами, сложность <math>O(mn)</math>.
 
* [[Алгоритм Беллмана-Форда]] для ориентированных графов с произвольными весами, сложность <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>.<ref>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.</ref>
+
* [[Алгоритм Δ-шагания]] для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами <math>O(n + m + dL)</math>, параллельная сложность <math>O((dL + \ln n) \ln n</math> со средней работой <math>O(n + m + dL \ln n)</math>.<ref>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.</ref>
 
* [[Алгоритм Торупа]] для неориентированных графов с положительными целыми весами, сложность <math>O(m)</math>.<ref name=thorup />
 
* [[Алгоритм Торупа]] для неориентированных графов с положительными целыми весами, сложность <math>O(m)</math>.<ref name=thorup />
  
−
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>d</math> – максимальная степень вершины, <math>L</math> – максимальная длина кратчайшего пути.
+
Обозначения: <math>m</math> – число рёбер, <math>n</math> – число вершин, <math>d</math> – максимальная степень вершины, <math>L</math> – максимальный суммарный вес кратчайшего пути.
  
 
== Ссылки ==
 
== Ссылки ==
  
 
<references />
 
<references />

Версия 16:46, 2 июня 2015

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. ↑ 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.
  2. ↑ 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.
  3. ↑ 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.
  4. ↑ 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.
Источник — https://algowiki-project.org/w/ru/index.php?title=Поиск_кратчайшего_пути_от_одной_вершины_(SSSP)&oldid=1672