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

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

Алгоритм Дейкстры для поиска кратчайшего пути между 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] [9]} Фредман и Тарьян в 1984 году предложили приоритетную очередь с кучей Фибоначчи для оптимизации сложности времени выполнения до . Это асимптотически самый быстрый известный алгоритм поиска кратчайшего пути с одним источником для произвольных направленных графов с неограниченными неотрицательными весами. Однако специализированные случаи (такие как ограниченные/целочисленные веса, направленные ациклические графы и т. д.) могут быть улучшены еще больше. Если разрешена предварительная обработка, такие алгоритмы, как иерархии сжатия, могут быть на семь порядков быстрее.${\displaystyle \Theta (|V|^{2})}$ ${\displaystyle |V|}$${\displaystyle \Theta (|E|+|V|\log |V|)}$

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

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

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

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

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

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

1. Создайте набор всех непосещенных узлов: непосещенный набор.
2. Назначьте каждому узлу расстояние от начального значения: для начального узла оно равно нулю, а для всех остальных узлов — бесконечности, поскольку изначально путь к этим узлам неизвестен. Во время выполнения расстояние до узла N — это длина кратчайшего пути, обнаруженного до сих пор между начальным узлом и N . ^[18]
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) каждый посещенный узел содержит кратчайшее расстояние от начального узла.

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

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

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

В следующем псевдокоде 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 соединяются с целью и лежат на разных кратчайших путях через цель (потому что стоимость ребра одинакова в обоих случаях), то и r , и source добавляются в prev[ target ] . Когда алгоритм завершается, структура данных prev[] описывает граф, который является подмножеством исходного графа с некоторыми удаленными ребрами. Ее ключевым свойством является то, что если алгоритм был запущен с некоторым начальным узлом, то каждый путь от этого узла до любого другого узла в новом графе является кратчайшим путем между этими узлами графа, и все пути этой длины из исходного графа присутствуют в новом графе. Затем, чтобы фактически найти все эти кратчайшие пути между двумя заданными узлами, будет работать алгоритм поиска пути на новом графе, такой как поиск в глубину .

Очередь с минимальным приоритетом — это абстрактный тип данных, который обеспечивает 3 основные операции: add_with_priority() , reduce_priority() и extract_min() . Как упоминалось ранее, использование такой структуры данных может привести к более быстрому времени вычислений, чем использование базовой очереди. В частности, куча Фибоначчи ^[19] или очередь Бродала предлагают оптимальные реализации для этих 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]

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

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

Для доказательства корректности алгоритма Дейкстры можно использовать математическую индукцию по количеству посещённых узлов. ^[22]

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

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

Предполагая, что гипотеза верна для посещённых узлов, чтобы показать, что она верна для узлов, пусть u будет следующим посещённым узлом, т. е. узлом с минимальным . Утверждается, что это кратчайшее расстояние от источника до u .${\displaystyle к}$${\displaystyle к+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} Этот вариант имеет те же наихудшие границы, что и общий вариант, но на практике поддерживает меньшую приоритетную очередь, ускоряя операции очереди. ^[12]

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

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

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

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

Помимо простого вычисления расстояний и путей, алгоритм Дейкстры может быть использован для сортировки вершин по их расстоянию от заданной начальной вершины. В 2023 году Хойплер, Рожон, Тетек, Хладик и Тарьян (один из изобретателей кучи 1984 года) доказали, что для этой задачи сортировки на положительно взвешенном ориентированном графе версия алгоритма Дейкстры со специальной структурой данных кучи имеет время выполнения и количество сравнений, которые находятся в пределах постоянного множителя оптимального среди алгоритмов , основанных на сравнении, для той же задачи сортировки на том же графе и начальной вершине, но с переменными весами ребер. Для достижения этого они используют кучу, основанную на сравнении, стоимость возврата/удаления минимального элемента из кучи логарифмически зависит от количества элементов, вставленных после нее, а не от количества элементов в куче. ^{[27] [28]}

Когда веса дуг являются небольшими целыми числами (ограниченными параметром ), для увеличения скорости можно использовать специализированные очереди. Первым алгоритмом этого типа был алгоритм Дайала ^[29] для графов с положительными целыми весами ребер, который использует очередь из блоков для получения времени выполнения . Использование дерева Ван Эмде Боаса в качестве приоритетной очереди приводит к увеличению сложности до . ^[30] Другой интересный вариант, основанный на сочетании новой кучи с основанием и известной кучи Фибоначчи, работает за время . ^[30] Наконец, лучшие алгоритмы в этом особом случае работают за ^[31] время и время. ^[32]${\displaystyle С}$${\displaystyle O(|E|+|V|C)}$${\displaystyle O(|E|+|V|\log C/\log \log |V|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 .

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

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

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

Задача 2. Найти путь минимальной общей длины между двумя заданными узлами P и Q. Мы используем тот факт, что если R — узел на минимальном пути из P в Q , то знание последнего подразумевает знание минимального пути из P в 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 . doi : 10.1137/S0097539795288246. S2CID  5221089.
• Торуп, Миккель (1999). «Ненаправленные кратчайшие пути с одним источником и положительными целыми весами за линейное время». Журнал ACM . 46 (3): 362–394 . doi : 10.1145/316542.316548 . S2CID  207654795.

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

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