Алгоритм Дейкстры

Не путать с алгоритмом проецирования Дикстры .

Алгоритм Дейкстры

Алгоритм Дейкстры для поиска кратчайшего пути между a и b . Он выбирает непосещенную вершину с наименьшим расстоянием, вычисляет расстояние через нее до каждого непосещенного соседа и обновляет расстояние до соседа, если оно меньше. Отметить посещение (выделено красным), когда закончилось общение с соседями.
Сорт	Алгоритм поиска Жадный алгоритм Динамическое программирование
Структура данных	График Обычно используется с приоритетной очередью или кучей для оптимизации.
Худшая производительность	$\Theta (|E|+|V|\log |V|)$

Алгоритм Дейкстры ( / ˈd aɪ k s t r ə z / . DYKE -strəz ) — алгоритм поиска путей между узлами во взвешенном графе , который может представлять, например, дорожные сети кратчайших Он был задуман ученым-компьютерщиком Эдсгером В. Дейкстрой в 1956 году и опубликован три года спустя.

Алгоритм Дейкстры находит кратчайший путь от заданного исходного узла до любого другого узла. Его также можно использовать для поиска кратчайшего пути к определенному узлу назначения путем завершения алгоритма, как только станет известен кратчайший путь к узлу назначения. Например, если узлы графа представляют собой города, а стоимость ребер представляет собой средние расстояния между парами городов, соединенных прямой дорогой, то алгоритм Дейкстры можно использовать для поиска кратчайшего маршрута между одним городом и всеми остальными городами. Распространенным применением алгоритмов кратчайшего пути являются протоколы сетевой маршрутизации , в первую очередь IS-IS (от промежуточной системы к промежуточной системе) и OSPF (сначала открывайте кратчайший путь). Он также используется в качестве подпрограммы в других алгоритмах, таких как алгоритм Джонсона .

Алгоритм использует структуру данных очереди с минимальным приоритетом для выбора кратчайших известных на данный момент путей. До того, как были обнаружены более совершенные структуры очередей с приоритетами, оригинальный алгоритм Дейкстры работал в $\Theta (|V|^{2})$ время , где $|V|$ это количество узлов. Идея этого алгоритма также изложена в Leyzorek et al. 1957 год . Фредман и Тарьян в 1984 году предложили использовать очередь с приоритетами кучи Фибоначчи для оптимизации сложности времени выполнения. $\Theta (|E|+|V|\log |V|)$. Это асимптотически с одним источником самый быстрый из известных алгоритмов поиска кратчайшего пути для произвольных ориентированных графов с неограниченными неотрицательными весами. Однако специализированные случаи (такие как ограниченные/целочисленные веса, ориентированные ациклические графы и т. д.) действительно могут быть улучшены, как подробно описано в разделе «Специализированные варианты» . Кроме того, если разрешена предварительная обработка, такие алгоритмы, как сжимающие иерархии, могут работать на семь порядков быстрее.

Алгоритм Дейкстры обычно используется на графах, где веса ребер представляют собой положительные целые или действительные числа. Его можно обобщить на любой граф, где веса ребер частично упорядочены , при условии, что последующие метки (последующая метка создается при прохождении ребра) монотонно не убывают.

Во многих областях, особенно в области искусственного интеллекта , алгоритм Дейкстры или его вариант известен как поиск с равномерной стоимостью и сформулирован как пример более общей идеи поиска по принципу «наилучший результат» .

История

Какой самый короткий путь доехать из Роттердама в Гронинген вообще: из данного города в данный город. Это алгоритм кратчайшего пути , который я разработал примерно за двадцать минут. Однажды утром я ходил по магазинам в Амстердаме со своей молодой невестой, и уставшие, мы сели на террасе кафе, чтобы выпить чашку кофе, и я просто думал о том, смогу ли я это сделать, а затем разработал алгоритм кратчайшего пути. . Как я уже сказал, это было двадцатиминутное изобретение. Фактически, оно было опубликовано в 59-м, три года спустя. Издание до сих пор читабельно, оно, на самом деле, весьма приятное. Одна из причин, по которой он так хорош, заключалась в том, что я разработал его без карандаша и бумаги. Позже я узнал, что одним из преимуществ проектирования без карандаша и бумаги является то, что вам практически приходится избегать всех сложностей, которых можно избежать. В конце концов, к моему величайшему изумлению, этот алгоритм стал одним из краеугольных камней моей славы.

- Эдсгер Дейкстра, в интервью Филипу Л. Фране, Communications of the ACM, 2001 г.

Дейкстра задумался о задаче о кратчайшем пути, когда работал в Математическом центре в Амстердаме в 1956 году, чтобы продемонстрировать возможности нового компьютера под названием ARMAC. программистом Его цель состояла в том, чтобы выбрать и проблему, и решение (которое будет создано компьютером), которое могли бы понять люди, не умеющие работать с компьютерами. Он разработал алгоритм кратчайшего пути и позже реализовал его для ARMAC для слегка упрощенной транспортной карты 64 городов Нидерландов (64, так что 6 бит будет достаточно для кодирования номера города). Год спустя он столкнулся с еще одной проблемой от инженеров-аппаратистов, работавших над следующим институтским компьютером: минимизировать количество проводов, необходимых для соединения контактов на задней панели машины. В качестве решения он заново открыл алгоритм, известный как алгоритм минимального связующего дерева Прима (известный ранее Ярнику , а также переоткрытый Примом ). Дейкстра опубликовал алгоритм в 1959 году, через два года после Прима и через 29 лет после Ярника.

Алгоритм

Иллюстрация алгоритма Дейкстры, находящего путь от начального узла (левый нижний, красный) к целевому узлу (правый верхний, зеленый) в робота задаче планирования движения . Открытые узлы представляют собой «предварительный» набор (также известный как набор «непосещенных» узлов). Закрашенные узлы — это посещенные узлы, цвет которых обозначает расстояние: чем зеленее, тем ближе. Узлы во всех различных направлениях исследуются одинаково, выглядя более или менее как круговой волновой фронт , поскольку алгоритм Дейкстры использует эвристику выбора кратчайшего известного пути.

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

1. Отметьте все узлы как непосещенные. Создайте набор всех непосещенных узлов, называемый непосещенным набором .
2. Присвойте каждому узлу расстояние от начального значения: для начального узла оно равно нулю, а для всех остальных узлов — бесконечности, поскольку изначально путь к этим узлам неизвестен. Во время выполнения алгоритма расстояние узла N — это длина обнаруженного на данный момент кратчайшего пути между начальным узлом N. и
3. Из непосещенного набора выберите текущий узел с наименьшим конечным расстоянием; изначально это будет начальный узел, расстояние которого равно нулю. Если непосещенный набор пуст или содержит только узлы с бесконечным расстоянием (которые недостижимы), то алгоритм завершается, переходя к шагу 6. ​​Если нас интересует только путь к целевому узлу, мы можем завершить здесь, если текущий узел является целевым узлом. В противном случае мы можем продолжить поиск кратчайших путей ко всем достижимым узлам.
4. Для текущего узла рассмотрим всех его непосещенных соседей и обновим их расстояния через текущий узел; сравните вновь вычисленное расстояние с тем, которое в настоящее время назначено соседу, и назначьте ему меньшее. Например, если текущий узел A отмечен расстоянием 6, а ребро, соединяющее его с соседом B, имеет длину 2, то расстояние до B через A равно 6 + 2 = 8. Если B ранее был отмечен знаком расстояние больше 8, затем обновите его до 8 (путь от B через A короче). В противном случае сохраните текущее расстояние (путь к B через A не самый короткий).
5. Когда мы закончим рассматривать всех непосещенных соседей текущего узла, пометьте текущий узел как посещенный и удалите его из набора непосещенных. Это сделано для того, чтобы посещенный узел никогда не проверялся снова, и это правильно, поскольку расстояние, записанное в текущем узле, минимально (как обеспечивается на шаге 3) и, следовательно, является окончательным. Вернитесь к шагу 3.
6. После выхода из цикла (шаги 3–5) каждый посещенный узел будет содержать кратчайшее расстояние от начального узла.

Описание

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

Предположим, вы хотите найти кратчайший путь между двумя перекрестками на карте города: начальной точкой и пунктом назначения . Алгоритм Дейкстры изначально отмечает расстояние (от начальной точки) до каждого второго пересечения на карте с бесконечностью . Это сделано не для того, чтобы подразумевать, что расстояние бесконечно, а для того, чтобы отметить, что эти перекрестки еще не посещены. Некоторые варианты этого метода оставляют расстояния до пересечений немаркированными . Теперь выберите текущее пересечение на каждой итерации. Для первой итерации текущий перекресток будет начальной точкой, а расстояние до него (метка перекрестка) будет равно нулю . Для последующих итераций (после первой) текущий перекресток будет ближайшим к начальной точке непосещенным пересечением (его будет легко найти).

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

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

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

Псевдокод

следующем псевдокоде В dist — это массив, содержащий текущие расстояния от источник к другим вершинам, т.е. dist[ u ] — текущее расстояние от источника до вершины ты . Массив prev содержит указатели на узлы предыдущего перехода на кратчайшем пути от источника к данной вершине (эквивалентно, это следующий переход на пути от данной вершины к источнику). Код u ← вершина в Q с min dist[u] , ищет вершину ты в множестве вершин Q, который имеет наименьшее количество dist[ u ] . значение Graph.Edges( u , v ) возвращает длину ребра, соединяющего (т. е. расстояние между) двух соседних узлов. ты и в . Переменная alt в строке 14 — это длина пути от исходный узел к соседнему узлу v если бы это произошло ты . Если этот путь короче текущего кратчайшего пути, записанного для v , то расстояние v обновляется до все .

Демонстрация алгоритма Дейкстры, основанного на евклидовом расстоянии. Красные линии — это покрытие кратчайшего пути, т. е. соединяющее u и prev[ u ]. Синие линии показывают, где происходит расслабление, т. е. соединение v с узлом u в Q , что дает более короткий путь от источника до v .

 1  function Dijkstra(Graph, source):
 2     
 3      for each vertex v in Graph.Vertices:
 4          dist[v] ← INFINITY
 5          prev[v] ← UNDEFINED
 6          add v to Q
 7      dist[source] ← 0
 8     
 9      while Q is not empty:
10          u ← vertex in Q with minimum dist[u]
11          remove u from Q
12         
13          for each neighbor v of u still in Q:
14              alt ← dist[u] + Graph.Edges(u, v)
15              if alt < dist[v]:
16                  dist[v] ← alt
17                  prev[v] ← u
18
19      return dist[], prev[]

Если нас интересует только кратчайший путь между вершинами источник и target , мы можем прекратить поиск после строки 10, если ты = цель . Теперь мы можем прочитать кратчайший путь из источник для цель путем обратной итерации:

1  S ← empty sequence
2  u ← target
3  if prev[u] is defined or u = source:          // Do something only if the vertex is reachable
4      while u is defined:                       // Construct the shortest path with a stack S
5          insert u at the beginning of S        // Push the vertex onto the stack
6          u ← prev[u]                           // Traverse from target to source

Теперь последовательность S — список вершин, составляющих один из кратчайших путей из источник для target или пустая последовательность, если пути не существует.

Более общей задачей было бы найти все кратчайшие пути между источник и target (может быть несколько разных одинаковой длины). Тогда вместо хранения только одного узла в каждой записи prev[] мы будем хранить все узлы, удовлетворяющие условию релаксации. Например, если оба р и источник подключения к цель , и оба они лежат на разных кратчайших путях через target (поскольку стоимость ребра одинакова в обоих случаях), то мы бы добавили оба р и источник для предыдущая [ цель ] . Когда алгоритм завершится, Структура данных prev[] фактически будет описывать граф, который является подмножеством исходного графа с удаленными некоторыми ребрами. Его ключевым свойством будет то, что если алгоритм был запущен с некоторым начальным узлом, то каждый путь от этого узла к любому другому узлу в новом графе будет кратчайшим путем между этими узлами в исходном графе, и все пути этой длины от исходный график будет присутствовать в новом графике. Затем, чтобы на самом деле найти все эти кратчайшие пути между двумя заданными узлами, мы должны использовать алгоритм поиска пути на новом графе, например поиск в глубину .

Использование приоритетной очереди

Очередь с минимальным приоритетом — это абстрактный тип данных, который обеспечивает три основные операции: add_with_priority() , уменьшение_приоритета() и экстракт_мин() . Как упоминалось ранее, использование такой структуры данных может привести к сокращению времени вычислений, чем использование базовой очереди. В частности, куча Фибоначчи. или очередь Brodal предлагают оптимальные реализации для этих трех операций. Поскольку алгоритм немного отличается по внешнему виду, он упоминается здесь и в псевдокоде:

1   function Dijkstra(Graph, source):
2       create vertex priority queue Q
3
4       dist[source] ← 0                          // Initialization
5       Q.add_with_priority(source, 0)            // associated priority equals dist[·]
6
7       for each vertex v in Graph.Vertices:
8           if v ≠ source
9               prev[v] ← UNDEFINED               // Predecessor of v
10              dist[v] ← INFINITY                // Unknown distance from source to v
11              Q.add_with_priority(v, INFINITY)
12
13
14      while Q is not empty:                     // The main loop
15          u ← Q.extract_min()                   // Remove and return best vertex
16          for each neighbor v of u:             // Go through all v neighbors of u
17              alt ← dist[u] + Graph.Edges(u, v)
18              if alt < dist[v]:
19                  prev[v] ← u
20                  dist[v] ← alt
21                  Q.decrease_priority(v, alt)
22
23      return dist, prev

Вместо заполнения очереди приоритетов всеми узлами на этапе инициализации также можно инициализировать ее так, чтобы она содержала только источник ; затем внутри if alt < dist[v] блок, уменьшение_приоритета() становится add_with_priority() , если узел еще не находится в очереди.

Еще одна альтернатива — безоговорочное добавление узлов в приоритетную очередь и вместо этого проверка после извлечения ( u ← Q.extract_min()), что он больше не посещает или что более короткое соединение еще не найдено в if alt < dist[v] блокировать. Это можно сделать, дополнительно извлекая связанный приоритет. p из очереди и только дальнейшая обработка if p == dist[u] внутри while Q is not empty петля.

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

Доказательство правильности

Чтобы доказать корректность алгоритма Дейкстры, мы действуем методом математической индукции по числу посещенных узлов.

Инвариантная гипотеза : для каждого посещенного узла v , dist[v] это кратчайшее расстояние от источник для v и для каждого непосещенного узла в , dist[u] это кратчайшее расстояние от источник для u при путешествии только через посещенные узлы или бесконечность, если такого пути не существует. (Примечание: мы не предполагаем dist[u] - фактическое кратчайшее расстояние для непосещенных узлов, а dist[v] это фактическое кратчайшее расстояние)

Базовый случай :

Базовый случай — когда есть только один посещенный узел, источник . Его расстояние определяется как ноль, что является кратчайшим расстоянием, поскольку отрицательные веса не допускаются. Следовательно, гипотеза верна.

Индуктивный шаг :

Предположим, что гипотеза справедлива для $k$ посещенные узлы. Мы хотим показать, что это справедливо для $k+1$ узлы. Позволять u — следующий посещенный узел согласно алгоритму, т.е. узел с минимальным dist[u]. Мы утверждаем, что dist[u] это кратчайшее расстояние от источник для в .

Для доказательства этого утверждения поступим от противного. Если существовал более короткий путь, то этот более короткий путь либо содержит еще один непосещенный узел, либо нет.

• В первом случае пусть w будет первым непосещенным узлом на этом более коротком пути. По предположению индукции кратчайшие пути из источник для ты и w через посещенные узлы имеют только затраты dist[u] и dist[w] соответственно. Это означает стоимость перехода от источник для через ​ w имеет стоимость не менее dist[w] + минимальная стоимость перехода от в это ты . Поскольку краевые затраты положительны, минимальная стоимость перехода от в это у — положительное число. Однако, dist[u] самое большее dist[w] потому что в противном случае очередь приоритетов выбрала бы w вместо v. Это противоречие, поскольку уже установлено, что dist[w] + положительное число < dist[u].

• В последнем случае пусть w — предпоследний узел на кратчайшем пути. Это означает dist[w] + Graph.Edges[w,u] < dist[u]. Это противоречие, потому что к тому времени w посещен, он должен был установить dist[u] максимум dist[w] + Graph.Edges[w,u].

Для всех остальных посещенных узлов в , dist[v] уже известно, что это кратчайшее расстояние от уже источник , из-за индуктивной гипотезы, и эти значения не изменились.

После обработки u , по-прежнему будет верно, что для каждого непосещенного узла В , dist[w] будет кратчайшее расстояние от источник для w используя только посещенные узлы. Если бы существовал более короткий путь, который не использовал бы u , мы бы нашли его раньше, и если бы существовал более короткий путь, используя мы бы обновили его при обработке в .

После посещения всех узлов определяется кратчайший путь из источник на любой узел v состоит только из посещенных узлов. Поэтому, dist[v] это кратчайшее расстояние.

Время работы

Границы времени работы алгоритма Дейкстры на графе с ребрами E и вершинами V можно выразить как функцию количества ребер, обозначаемую $|E|$, а количество вершин обозначается $|V|$, используя обозначение big-O . используемой для представления набора Q. Граница сложности зависит главным образом от структуры данных , В дальнейшем верхние оценки можно упростить, поскольку $|E|$ является $O(|V|^{2})$ для любого простого графа, но это упрощение не учитывает тот факт, что в некоторых задачах другие верхние границы $|E|$ может держаться.

Для любой структуры данных для набора вершин Q время выполнения находится в

$\Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),$

где $T_{\mathrm {dk} }$ и $T_{\mathrm {em} }$ — это сложности операций уменьшения ключа и извлечения минимума в Q соответственно.

Самая простая версия алгоритма Дейкстры сохраняет множество вершин Q как связанный список или массив, а ребра — как смежности список или матрицу . В этом случае extract-minimum — это просто линейный поиск по всем вершинам в Q , поэтому время выполнения равно $\Theta (|E|+|V|^{2})=\Theta (|V|^{2})$.

Для разреженных графов , то есть графов с гораздо меньшим количеством $|V|^{2}$ ребра, алгоритм Дейкстры может быть реализован более эффективно, если хранить граф в виде списков смежности и использовать самобалансирующееся двоичное дерево поиска , двоичную кучу , парную кучу или кучу Фибоначчи в качестве приоритетной очереди для эффективной реализации извлечения минимума. Чтобы эффективно выполнять шаги уменьшения ключа в двоичной куче, необходимо использовать вспомогательную структуру данных, которая сопоставляет каждую вершину с ее положением в куче и поддерживать эту структуру в актуальном состоянии при приоритетной очереди Q. изменении При использовании самобалансирующегося двоичного дерева поиска или двоичной кучи алгоритм требует

$\Theta ((|E|+|V|)\log |V|)$

время в худшем случае; для связных графов эту временную границу можно упростить до $\Theta (|E|\log |V|)$. Куча Фибоначчи улучшает это до

$\Theta (|E|+|V|\log |V|).$

При использовании двоичных куч средняя временная сложность случая ниже, чем в худшем случае: если предположить, что стоимость ребер рассчитывается независимо от общего распределения вероятностей , ожидаемое количество операций уменьшения ключа ограничено $\Theta (|V|\log(|E|/|V|))$, что дает общее время работы

$O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).$

Практическая оптимизация и бесконечные графики

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

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

procedure uniform_cost_search(start) is
    node ← start
    frontier ← priority queue containing node only
    expanded ← empty set
    do
        if frontier is empty then
            return failure
        node ← frontier.pop()
        if node is a goal state then
            return solution(node)
        expanded.add(node)
        for each of node's neighbors n do
            if n is not in expanded and not in frontier then
                frontier.add(n)
            else if n is in frontier with higher cost
                replace existing node with n

Сложность этого алгоритма можно выразить альтернативным способом для очень больших графов: когда C ^* длина кратчайшего пути от начального узла до любого узла, удовлетворяющего предикату «цель», каждое ребро имеет стоимость не менее ε , а количество соседей на узел ограничено b , тогда время и пространство алгоритма для наихудшего случая сложность оба находятся в O ( b ^{1+⌊ C * ⁄ ε ⌋} ) .

Дальнейшая оптимизация алгоритма Дейкстры для случая с одной целью включает двунаправленные варианты, целевые варианты, такие как алгоритм A * (см. § Связанные проблемы и алгоритмы ), обрезку графа для определения того, какие узлы с большой вероятностью сформируют средний сегмент кратчайших путей. (маршрутизация на основе охвата) и иерархическая декомпозиция входного графа, которая сводит s – t маршрутизацию к соединению s и t с их соответствующими « транзитными узлами » с последующим вычислением кратчайшего пути между этими транзитными узлами с использованием «шоссе». Для оптимального практического решения конкретных задач могут потребоваться комбинации таких методов.

Специализированные варианты

Когда веса дуг являются небольшими целыми числами (ограниченными параметром $C$), специализированные очереди, использующие этот факт, можно использовать для ускорения алгоритма Дейкстры. Первым алгоритмом этого типа был алгоритм Дайала ( Dial 1969 ) для графов с положительными целочисленными весами ребер, который использует очередь сегментов для получения времени выполнения. $O(|E|+|V|C)$. Использование дерева Ван Эмде Боаса в качестве очереди приоритетов усложняет задачу. $O(|E|\log \log C)$ ( Ахуджа и др., 1990 ). Еще один интересный вариант, основанный на сочетании новой поразрядной кучи и известной кучи Фибоначчи, работает во времени. $O(|E|+|V|{\sqrt {\log C}})$ ( Ахуджа и др., 1990 ). Наконец, лучшими алгоритмами в этом частном случае являются следующие. Алгоритм, данный ( Thorup 2000 ), работает в $O(|E|\log \log |V|)$ время и алгоритм, данный ( Raman 1997 ), работает в $O(|E|+|V|\min\{(\log |V|)^{1/3+\varepsilon },(\log C)^{1/4+\varepsilon }\})$ время.

Связанные проблемы и алгоритмы

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

Алгоритм Дейкстры обычно является принципом работы протоколов маршрутизации по состоянию канала , OSPF и IS-IS наиболее распространенными из которых являются .

В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда можно использовать на графах с отрицательными весами ребер, если граф не содержит отрицательных циклов, достижимых из исходной вершины s . Наличие таких циклов означает, что кратчайшего пути не существует, поскольку общий вес становится меньше при каждом прохождении цикла. (Это утверждение предполагает, что «пути» могут повторять вершины. В теории графов это обычно не допускается. В теоретической информатике это часто допускается.) Алгоритм Дейкстры можно адаптировать для обработки ребер с отрицательным весом, комбинируя его с алгоритм Беллмана-Форда (для удаления отрицательных фронтов и обнаружения отрицательных циклов); такой алгоритм называется алгоритмом Джонсона .

Алгоритм A* представляет собой обобщение алгоритма Дейкстры, которое сокращает размер подграфа, который необходимо исследовать, если доступна дополнительная информация, обеспечивающая нижнюю границу «расстояния» до цели.

Процесс, лежащий в основе алгоритма Дейкстры, аналогичен жадному процессу, используемому в алгоритме Прима . Цель Прима — найти минимальное связующее дерево , которое соединяет все узлы графа; Дейкстру интересуют только два узла. Prim's не оценивает общий вес пути от начального узла, а только отдельные ребра.

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

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

Перспектива динамического программирования

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

Фактически, объяснение Дейкстры логики алгоритма а именно

Задача 2. Найти путь минимальной общей длины между двумя заданными узлами. $P$ и $Q$.

Мы используем тот факт, что если $R$ — узел на минимальном пути из $P$ к $Q$, знание последнего предполагает знание минимального пути из $P$ к $R$.

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

См. также

• Алгоритм поиска A*
• Алгоритм Беллмана – Форда
• Евклидов кратчайший путь
• Алгоритм Флойда – Уоршалла
• Алгоритм Джонсона
• Задача о самом длинном пути
• Параллельный алгоритм поиска кратчайшего пути для всех пар

Ссылки

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Раздел 24.3: Алгоритм Дейкстры». Введение в алгоритмы (второе изд.). MIT Press и МакГроу-Хилл . стр. 595–601. ISBN  0-262-03293-7 .
• Дайал, Роберт Б. (1969). «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]» . Коммуникации АКМ . 12 (11): 632–633. дои : 10.1145/363269.363610 . S2CID   6754003 .
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1984). Кучи Фибоначчи и их использование в усовершенствованных алгоритмах оптимизации сети . 25-й ежегодный симпозиум по основам информатики. ИИЭЭ . стр. 338–346. дои : 10.1109/SFCS.1984.715934 .
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. дои : 10.1145/28869.28874 . S2CID   7904683 .
• Жан, Ф. Бенджамин; Полдень, Чарльз Э. (февраль 1998 г.). «Алгоритмы кратчайшего пути: оценка с использованием реальных дорожных сетей». Транспортная наука . 32 (1): 65–73. дои : 10.1287/trsc.32.1.65 . S2CID   14986297 .
• Лейзорек, М.; Грей, РС; Джонсон, А.А.; Ладью, туалет; Микер-младший, старший офицер; Петри, РМ; Зейтц, Р.Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи . Кливленд, Огайо: Технологический институт Кейса.
• Кнут, DE (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. дои : 10.1016/0020-0190(77)90002-3 .
• Ахуджа, Равиндра К.; Мельхорн, Курт; Орлин, Джеймс Б.; Тарьян, Роберт Э. (апрель 1990 г.). «Быстрые алгоритмы решения задачи кратчайшего пути» (PDF) . Журнал АКМ . 37 (2): 213–223. дои : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID   5499589 .
• Раман, Раджив (1997). «Недавние результаты по задаче о кратчайших путях из одного источника» . Новости СИГАКТ . 28 (2): 81–87. дои : 10.1145/261342.261352 . S2CID   18031586 .
• Торуп, Миккель (2000). «Очереди с приоритетом ОЗУ». SIAM Journal по вычислительной технике . 30 (1): 86–109. дои : 10.1137/S0097539795288246 . S2CID   5221089 .
• Торуп, Миккель (1999). «Ненаправленные кратчайшие пути с одним источником и положительными целочисленными весами за линейное время» . Журнал АКМ . 46 (3): 362–394. дои : 10.1145/316542.316548 . S2CID   207654795 .

Внешние ссылки

• Интервью по устной истории с Эдсгером В. Дейкстрой , Институт Чарльза Бэббиджа , Университет Миннесоты, Миннеаполис
• Реализация алгоритма Дейкстры с использованием TDD , Роберт Сесил Мартин , Блог Clean Code