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

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

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

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

Алгоритм Дейкстры находит кратчайший путь от заданного исходного узла до каждого другого узла. ^{[7] : 196–206} Его также можно использовать для поиска кратчайшего пути до определенного конечного узла, завершая алгоритм, как только кратчайший путь до конечного узла будет известен. Например, если узлы графа представляют города, а стоимости ребер представляют средние расстояния между парами городов, соединенных прямой дорогой, то алгоритм Дейкстры можно использовать для поиска кратчайшего маршрута между одним городом и всеми другими городами. Распространенным применением алгоритмов кратчайшего пути являются протоколы сетевой маршрутизации , в первую очередь IS-IS (Intermediate System to Intermediate System) и OSPF (Open Shortest Path First). Он также используется в качестве подпрограммы в других алгоритмах, таких как алгоритм Джонсона .

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

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

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

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

—  Эдсгер Дейкстра, в интервью с Филиппом Л. Франа, Communications of the ACM, 2001 ^[5]

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

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

1. Создайте набор всех непосещенных узлов, называемый непосещенным набором .
2. Назначьте каждому узлу расстояние от начального значения: для начального узла оно равно нулю, а для всех остальных узлов — бесконечности, поскольку изначально путь к этим узлам неизвестен. Во время выполнения алгоритма расстояние до узла N — это длина кратчайшего пути, обнаруженного до сих пор между начальным узлом и N . ^[17]
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 ] — это текущее расстояние от источника до вершины u . Массив prev содержит указатели на узлы previous-hop на кратчайшем пути от источника до заданной вершины (эквивалентно, это следующий переход на пути от заданной вершины до источника). Код u ← vertex в Q с min dist[u] ищет вершину u в наборе вершин Q , которая имеет наименьшее значение dist[ u ] . Graph.Edges( u , v ) возвращает длину ребра, соединяющего (т. е. расстояние между) два соседних узла u и v . Переменная alt в строке 14 — это длина пути от исходного узла до соседнего узла v, если бы он проходил через u . Если этот путь короче текущего кратчайшего пути, записанного для v , то расстояние v обновляется до alt . ^[7]

1 функция Дейкстры ( график , источник ): 2  3 для каждой вершины v в Graph.Vertices : 4 dist[ v ] ← БЕСКОНЕЧНОСТЬ 5 предыдущая[ v ] ← НЕОПРЕДЕЛЕНО 6 добавить v к Q 7 dist[ source ] ← 0 8  9, пока  Q не пусто:10 u ← вершина в Q с минимальным расстоянием[u]11 удалить u из Q12 13 для каждого соседа v u , все еще находящегося в Q :14 alt ← dist[ u ] + Граф.Ребра( u , v )15 , если  alt < dist[ v ]:16 dist[ v ] ← alt
17 prev[ v ] ← u1819 возврат dist[], prev[]

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

1 S ← пустая последовательность2 u ← target
3 if prev[ u ] is defined or  u = source : // Сделать что-то, только если вершина достижима
4 while  u is defined: // Построить кратчайший путь с помощью стека S
5 insert u at beginning S  // Поместить вершину в стек
6 u ← prev[ u ] // Переход от цели к источнику

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

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

Очередь с минимальным приоритетом — это абстрактный тип данных, который обеспечивает 3 основные операции: add_with_priority() , reduce_priority() и extract_min() . Как упоминалось ранее, использование такой структуры данных может привести к более быстрому времени вычислений, чем использование базовой очереди. В частности, куча Фибоначчи ^[18] или очередь Бродала предлагают оптимальные реализации для этих 3 операций. Поскольку алгоритм немного отличается внешне, он упоминается здесь, также в псевдокоде:

1 функция Дейкстры ( график , источник ):2 создать очередь приоритетов вершин Q34 dist[ source ] ← 0 // Инициализация
5 Q .add_with_priority( source , 0) // связанный приоритет равен dist[·]67 для каждой вершины v в Graph.Vertices :8 если  v ≠ источник
9 prev[ v ] ← UNDEFINED // Предшественник v
10 dist[ v ] ← БЕСКОНЕЧНОСТЬ // Неизвестное расстояние от источника до v11 Q.add_with_priority(v, INFINITY)121314 пока  Q не пуст: // Основной цикл
15 u ← Q .extract_min() // Удаляем и возвращаем лучшую вершину
16 для каждого соседа v вершины u : // Проходим по всем v соседям вершины u
17 alt ← dist[ u ] + Graph.Edges( u , v )18 если  alt < dist[ v ]:19 prev[ v ] ← u
20 dist[ v ] ← alt
21 Q .decrease_priority( v , alt )2223 возврат расст., пред.

Вместо заполнения очереди приоритетов всеми узлами на этапе инициализации, можно также инициализировать ее так, чтобы она содержала только source ; тогда внутри блока операция reduce_priority() становится операцией add_with_priority() , если узел еще не находится в очереди. ^{[7] : 198}if alt < dist[v]

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

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

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

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

Базовый вариант :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \Theta ((|E|+|V|)\log |V|)}$

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

${\displaystyle \Theta (|E|+|V|\log |V|).}$

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

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

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

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

процедура uniform_cost_search(start) — это узел ← начало frontier ← приоритетная очередь, содержащая только узел расширенный ← пустой набор сделать  , если граница пуста , то  вернуть ошибку узел ← граница.pop() если узел является целевым состоянием , то  вернуть решение(узел) расширенный.добавить(узел) для каждого из соседей узла n  сделать  , если  n не находится в расширенном состоянии и не находится на границе, то frontier.add( n ) иначе, если  n находится на границе с более высокой стоимостью заменить существующий узел на n

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

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

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

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

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

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

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

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

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

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

С точки зрения динамического программирования алгоритм Дейкстры представляет собой схему последовательного приближения, которая решает функциональное уравнение динамического программирования для задачи кратчайшего пути методом Рича . ^{[26] [27] [28]}

На самом деле, объяснение Дейкстрой логики, лежащей в основе алгоритма, ^[29], а именно:

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

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

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

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

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

На Викискладе есть медиафайлы по теме «Алгоритм Дейкстры» .

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