Уровень задачи

Поиск кратчайшего пути для всех пар вершин (APSP)

Материал из Алговики
Перейти к навигации Перейти к поиску


1 Постановка задачи

Пусть задан граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math], [math]e \in E[/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]v[/math] называется достижимой из вершины [math]u[/math], если существует хотя бы один путь [math]P(u, v)[/math]. Суммарный вес этого пути равен

[math] f(P(u, v)) = \sum_{i = 1}^k f(e_i). [/math]

Требуется для каждой пары вершины [math](u, v)[/math], для которой вершина [math]v[/math] достижима из вершины [math]u[/math], указать путь [math]P^*(u, v)[/math], имеющий наименьший возможный суммарный вес:

[math] f^*(u, v) = f(P^*(u, v)) = \min f(P(u, v)). [/math]

Название задачи на английском языке – «All Pairs Shortest Path» (APSP).

2 Варианты задачи

Если требуется найти кратчайшие пути лишь от одной, а не от всех вершин – см. поиск кратчайшего пути от одной вершины.

Задача может быть поставлена как для ориентированного, так и для неориентированного графа. Приведённая постановка задачи применима в обоих случаях.

В зависимости от ограничений на возможные значения весов различают следующие случаи.

  • Единичные веса. В этом случае задача существенно упрощается и может быть решена за квадратичное время алгоритмом поиска вширь.
  • Положительные целые веса. Задача также может быть решена за квадратичное время[1] (хотя и с большей константой).
  • Неотрицательные веса. Часто встречающееся на практике ограничение, когда вес ребра соответствует времени или стоимости прохождения участка маршрута и не может быть отрицательным.
  • Произвольные веса. Наиболее общая постановка. Граф не должен содержать циклов с отрицательным суммарным весом, иначе кратчайшего пути не существует.

В зависимости от способа организации вычислений возможны следующие варианты:

  • статический граф, полное вычисление всех кратчайших путей (классический подход);
  • вычисление онлайн[2]: производятся предварительные вычисления, далее путь между парой вершин вычисляется по запросу (такой подход уместен, если в реальности потребуется вычислить кратчайшие пути только для некоторых пар, но заранее набор этих пар неизвестен);
  • динамический граф[3]: рёбра и вершины могут добавляться и удаляться, при этом происходит пересчёт кратчайших расстояний (вариант подходит для постоянно меняющихся графов, например, для социальных сетей).

3 Описание входных и выходных данных

Входные данные: взвешенный граф [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]O(m + n)[/math].

Выходные данные (возможные варианты):

  1. для каждой пары вершины [math](u, v)[/math] исходного графа – последнее ребро [math]e^*_{uv} = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
  2. для каждой пары вершин [math](u, v)[/math] исходного графа – суммарный вес [math]f^*(u, v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n^2)[/math].

3.1 Преобразование выходных данных и поиск кратчайшего пути

Кратчайший путь от [math]u[/math] к [math]v[/math] может быть восстановлен за время [math]O(\left |P^*(u, v) \right |)[/math], если, начиная с вершины [math]v[/math], проходить рёбра [math]e^*_{uw}[/math] в обратном направлении до тех пор, пока не будет посещена вершина [math]u[/math].

Рёбра [math]e^*_{uv}[/math] могут быть восстановлены за время [math]O(mn)[/math] перебором рёбер для каждой вершины:

[math] e^*_{uv} \in \{ (w, v) \in E \mid f^*(u, v) = f^*(u, w) + f((v, w)) \}. [/math]

Перебор может осуществляться параллельно.

Для поиска кратчайших расстояний [math]f^*(u, v)[/math] по набору рёбер [math]e^*_{uv}[/math], необходимо для данной вершины [math]u[/math] построить дерево из рёбер [math]e^*_{uv}[/math] и выполнить на нём поиск в ширину за время [math]O(m)[/math] (с возможностью параллелизации), общее время для всех пар вершин – [math]O(mn)[/math].

4 Алгоритмы решения задачи

  • Алгоритм Джонсона[4] для ориентированных графов с произвольными весами, сложность [math]O(mn+ n^2 \ln n)[/math].
  • Алгоритм Флойда-Уоршелла[5][6][7] для ориентированных графов с произвольными весами, сложность [math]O(n^3)[/math].
  • Многократное применение любого алгоритма поиска кратчайшего пути от одной вершины:
    • Поиск в ширину (BFS) для ориентированных невзвешенных графов, сложность [math]O(mn)[/math].
    • Алгоритм Дейкстры[8][9] для ориентированных графов с неотрицательными весами, сложность [math]O(mn + n^2 \ln n)[/math].
    • Алгоритм Беллмана-Форда[10][11][12] для ориентированных графов с произвольными весами, сложность [math]O(mn^2)[/math].
    • Алгоритм Δ-шагания[13] для ориентированных графов с неотрицательными весами, средняя сложность на графах со случайными весами [math]O(n(n + m + dL))[/math], параллельная сложность [math]O((dL + \ln n) n \ln n[/math] со средней работой [math]O(n (n + m + dL \ln n))[/math].
    • Алгоритм Торупа[1] представляет собой теоретическое доказательство возможности решения задачи для неориентированных графов с положительными целыми весами за линейное время [math]O(mn)[/math].
    • В ориентированном ациклическом графе с произвольными весами алгоритм основан на топологической сортировке графа, сложность [math]O(mn)[/math].

Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин, [math]d[/math] – максимальная степень вершины, [math]L[/math] – максимальный суммарный вес кратчайшего пути.

5 Ресурс параллелизма

Задача может быть решена путём применения любого алгоритма поиска кратчайшего пути от одной вершины для всех вершин графа, при этом вычисления для различных вершин независимы и могут выполняться параллельно.

В связи с квадратичной сложностью выходных данных и более чем квадратичной сложностью вычислений, имеет смысл проводить предварительную обработку данных и использовать различные декомпозиции графа, сводя задачу к параллельному нахождению кратчайших путей на подграфах меньших размеров[14]:

Набор декомпозиций, который целесообразно использовать в конкретном случае, зависит от структуры графа и может быть определён только после её анализа.

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. ↑ Djidjev, Hristo N, Grammati E Pantziou, and Christos D Zaroliagis. “On-Line and Dynamic Algorithms for Shortest Path Problems.” In Proceedings of STACS 95, 193–204. Lecture Notes in Computer Science Vol. 900, Berlin, Heidelberg: Springer, 1995. doi:10.1007/3-540-59042-0_73.
  3. ↑ Demetrescu, Camil, and Giuseppe F Italiano. “Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.” Journal of Computer and System Sciences 72, no. 5 (August 2006): 813–37. doi:10.1016/j.jcss.2005.05.005.
  4. ↑ Johnson, Donald B. “Efficient Algorithms for Shortest Paths in Sparse Networks.” Journal of the ACM 24, no. 1 (January 1977): 1–13. doi:10.1145/321992.321993.
  5. ↑ Roy, Bernard. “Transitivité Et Connexité.” Comptes Rendus De l'Académie Des Sciences 249 (1959): 216–218.
  6. ↑ Warshall, Stephen. “A Theorem on Boolean Matrices.” Journal of the ACM 9, no. 1 (January 1, 1962): 11–12. doi:10.1145/321105.321107.
  7. ↑ Floyd, Robert W. “Algorithm 97: Shortest Path.” Communications of the ACM 5, no. 6 (June 1, 1962): 345. doi:10.1145/367766.368168.
  8. ↑ 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.
  9. ↑ 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.
  10. ↑ Bellman, Richard. “On a Routing Problem.” Quarterly of Applied Mathematics 16 (1958): 87–90.
  11. ↑ Ford, L R. Network Flow Theory. Rand.org, RAND Corporation, 1958.
  12. ↑ Moore, Edward F. “The Shortest Path Through a Maze,” International Symposium on the Theory of Switching, 285–92, 1959.
  13. ↑ 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.
  14. ↑ Banerjee, Dip Sankar, Ashutosh Kumar, Meher Chaitanya, Shashank Sharma, and Kishore Kothapalli. “Work Efficient Parallel Algorithms for Large Graph Exploration on Emerging Heterogeneous Architectures.” Journal of Parallel and Distributed Computing, December 2014. doi:10.1016/j.jpdc.2014.11.006.
Источник — https://algowiki-project.org/w/ru/index.php?title=Поиск_кратчайшего_пути_для_всех_пар_вершин_(APSP)&oldid=25404