Задача о кратчайшем пути

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Кратчайший путь (A, B, D, F) между вершинами A и F в неориентированном графе без весов.
Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.

Зада́ча о кратча́йшем пути́ (англ. shortest path problem) — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.

Кратчайшая (простая) цепь часто называется геодезической [1].

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения[⇨].

У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.

Значимость данной задачи определяется ее различными практическими применениями[⇨]. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Определение[править | править вики-текст]

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

Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин P = ( v_1, v_2, \ldots, v_n ) \in V \times V \times \ldots \times V, таких что v_i смежна с v_{i+1} для 1 \leq i < n. Такой путь P называется путем длиной n из вершины v_1 в v_n (i указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).

Пусть e_{i, j} — ребро соединяющее две вершины: v_i и v_j. Дана весовая функция f: E \rightarrow \mathbb{R}, которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф G. Тогда кратчайшим путем из вершины v в вершину v' будет называться путь P = ( v_1, v_2, \ldots, v_n ) (где v_1 = v и v_n = v'), который имеет минимальное значение суммы \sum_{i =1}^{n-1} f(e_{i, i+1}). Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.


Существуют различные постановки задачи о кратчайшем пути:

  • Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
  • Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
  • Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).

Задача о кратчайшем пути с учетом дополнительных ограничений[править | править вики-текст]

Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи[2]. Примеры таких задач:

  1. Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории исследования операций[3].
  2. Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути[4].
  3. Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей P = {p_1, \dots, p_m} такое, что для любого t_i \in R найдется путь p_j \in P, накрывающий его. R = {t_1, \dots, t_k} — множество некоторых путей в ориентированном графе G[5].
  4. Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмноржества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины[6].

Алгоритмы[править | править вики-текст]

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

  • Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса[7].
  • Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
  • Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
  • Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа[7].
  • Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
  • Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх.
  • Поиск кратчайшего пути на основе алгоритма Килдала[8].

В работе (Черкасский и др., 1993)[9] представлено ещё несколько алгоритмов для решения этой задачи.

Задача поиска кратчайшего пути из одной вершины во все остальные[править | править вики-текст]

В такой постановке задачи осуществляется поиск кратчайшего пути из вершины v во все остальные вершины на графе.

Взвешенный ориентированный граф[править | править вики-текст]

Алгоритм Сложность Автор
Поиск в ширину O(E)

Ориентированный граф с неотрицательными весами[править | править вики-текст]

Алгоритм Сложность Автор
- O(V2EL) Форд 1956
Алгоритм Беллмана — Форда O(VE) Беллман 1958[10], Мур 1959[11]
- O(V2 log V) Данциг 1958, Данциг 1960, Minty (cf. Pollack&Wiebenson 1960), Whiting&Hillier 1960
Алгоритм Дейкстры со списком. O(V2) Leyzorek et al. 1957[12], Дейкстра 1959[13]
Алгоритм Дейкстры с модифицированной двоичной кучей O((E + V) log V) -
. . . . . . . . .
Алгоритм Дейкстры с использованием фибоначчиевой кучи O(E + V log V) Фридман&Тарьян 1984[14], Фридман&Тарьян 1987[15]
- O(E log log L) Джонсон 1982, Карлссон&Поблете 1983
Алгоритм Габова O(E logE/V L) Габов 1983, Габов 1985
- O(E + V√log L) Ахуджа et al. 1990

Ориентированный граф с произвольными весами[править | править вики-текст]

Алгоритм Сложность Автор
Алгоритм Беллмана — Форда O(VE) Беллман[10], Мур[16]

Задача о кратчайшем пути между всеми парами вершин[править | править вики-текст]

Задача о кратчайшем пути между всеми парами вершин для невзвешенного ориентированного графа была поставлена Симбелом в 1953 году[17], который обнаружил, что она может быть решена за линейное количество манипуляций (умножения) с матрицей. Сложность такого алгоритма O(V4).

Так же для решения данной задачи существуют другие более быстрые алгоритмы, такие как Алгоритм Флойда — Уоршелла со сложностью O(V3), и Алгоритм Джонсона (является комбинацией алгоритмов Бэллмана-Форда и Дейкстры) со сложностью O(VE + V2 log V).

Применение[править | править вики-текст]

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

Картографические сервисы[править | править вики-текст]

Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OpenStreetMap. В обучающем видео от Google можно узнать различные эффективные алгоритмы, которые применяются в данной сфере[19].

Недетерминированная машина[править | править вики-текст]

Если представить недетерминированную абстрактную машину как граф, где вершины описывают состояния, а ребра определяют возможные переходы, тогда алгоритмы поиска кратчайшего пути могут быть применены для поиска оптимальной последовательности решений для достижения главной цели. Например, если вершинами являются состояния Кубика Рубика, а ребром представляет собой одно действие над кубиком, тогда алгоритм может быть применен для поиска решения с минимальным количеством ходов.

Сети дорог[править | править вики-текст]

Задача поиска кратчайшего пути на графе широко используется при определении наименьшего расстояния в сети дорог.

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

Для реализации подхода, где одни дороги важнее других, существует множество алгоритмов. Они решают задачу поиска кратчайшего пути намного быстрее, чем аналогичные на обычных графах. Подобные алгоритмы состоят из двух этапов:

  1. этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины (может длиться до нескольких дней, если работать с реальными данными). Обычно выполняется один раз и потом используются полученные данные.
  2. этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.

Самый быстрый алгоритм может решить данную задачу на дорогах Европы или Америки за доли микросекунды[21].

Другие подходы (техники), которые применяются в данной сфере:

Похожие задачи[править | править вики-текст]

Существуют задачи, которые похожи на задачу поиска кратчайшего пути на графе.

  • Задача коммивояжёра. Требуется найти кратчайший маршрут, проходящий через указанные города (вершины) хотя бы по одному разу с последующим возвратом в исходный город. Данная задача относится к классу NP-трудных задач в отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без циклов. Задача коммивояжёра решается неэффективно для больших наборов данных.
  • Задача канадского путешественника и задача стохастического поиска кратчайшего пути являются обобщением рассматриваемой задачи, в которых обходимый граф заранее полностью неизвестен и изменяется во времени или следующий проход по графу вычисляется на основе вероятностей.
  • Задача поиска кратчайшего пути, когда в графе происходят преобразования. Например, изменяется вес ребра или удаляется вершина[22].

Постановка задачи линейного программирования[править | править вики-текст]

Пусть дан направленный граф (V, A), где V — множество вершин и A — множество ребер, с начальной вершиной обхода s, конечной t и весами wij для каждого ребра (i, j) в A. Вес каждого ребра соответствует переменной программы xij.

Тогда задача ставится следующим образом: найти минимум функции F=\sum_{ij \in A} w_{ij} x_{ij}, где x_{ij} \ge 0, при условии что для всех i и j выполняется следующее неравенство: \sum_j x_{ij} - \sum_j x_{ji} = \begin{cases}1, &\text{if }i=s;\\ -1, &\text{if }i=t;\\ 0, &\text{ otherwise.}\end{cases}

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • Харари Ф. Глава 2. Графы // Теория графов / Под ред. Г. П. Гаврилова. — Издательство мир, 1973. — С. 27. — 300 с. — ISBN 5-354-00301-6.
  • Ричард Беллман (1958). «On a routing problem». Quarterly of Applied Mathematics 16: 87–90.
  • E. F. Moore (April 2–5, 195). «The shortest path through a maze» (Harvard University Press): 285–292.
  • M. Leyzorek, R. S. Gray, A. A. Gray, W. C. Ladew, S. R. Meaker, R. M. Petry, R. N. Seitz Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. — Cleveland, Ohio: Case Institute of Technology, 1957.
  • Shimbel, Alfonso (1953). «Structural parameters of communication networks». Bulletin of Mathematical Biophysics 15 (4): 501–507. DOI:10.1007/BF02476438.
  • Chen, Danny Z. (December 1996). «Developing algorithms and software for geometric path planning problems». ACM Computing Surveys 28 (4es): 18. DOI:10.1145/242224.242246.
  • Kroger, Martin (2005). «Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems». Computer Physics Communications 168 (168): 209–232. DOI:10.1016/j.cpc.2005.01.020.
  • Ladyzhensky Y., Popoff Y. (2006). «Algorithm to define the shortest paths between all nodes in a graph after compressing of two nodes. Proceedings of Donetsk national technical university, Computing and automation. Vol.107. Donetsk»: 68–75.