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

Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе

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

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

Определение

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

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

Позволять $E=\{e_{i,j}\}$ где $e_{i,j}$ является ребром, инцидентным обоим $v_{i}$ и $v_{j}$. Учитывая вещественную весовую функцию $f:E\rightarrow \mathbb {R}$и неориентированный (простой) граф $G$, кратчайший путь из $v$ к $v'$ это путь $P=(v_{1},v_{2},\ldots ,v_{n})$ (где $v_{1}=v$ и $v_{n}=v'$) это из всех возможных $n$ минимизирует сумму $\sum _{i=1}^{n-1}f(e_{i,i+1}).$ Когда каждое ребро графа имеет единичный вес или $f:E\rightarrow \{1\}$, это эквивалентно поиску пути с наименьшим количеством ребер.

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

• Задача о кратчайшем пути с одним источником , в которой нам нужно найти кратчайшие пути от исходной вершины v ко всем остальным вершинам графа.
• Задача о кратчайшем пути с одним пунктом назначения , в которой нам нужно найти кратчайшие пути от всех вершин ориентированного графа до одной целевой вершины v . Это можно свести к задаче о кратчайшем пути с одним источником, поменяв местами дуги в ориентированном графе.
• Задача о кратчайшем пути для всех пар , в которой нам нужно найти кратчайшие пути между каждой парой вершин v , v' в графе.

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

Алгоритмы

Существует несколько хорошо известных алгоритмов решения этой задачи и ее вариантов.

• Алгоритм Дейкстры решает задачу о кратчайшем пути с одним источником и неотрицательным весом ребра.
• Алгоритм Беллмана – Форда решает проблему одного источника, если веса ребер могут быть отрицательными.
• Алгоритм поиска A* ищет кратчайший путь для одной пары, используя эвристику, чтобы попытаться ускорить поиск.
• Алгоритм Флойда – Уоршалла находит все пары кратчайших путей.
• Алгоритм Джонсона решает все пары кратчайших путей и может быть быстрее, чем Флойд-Уоршалл на разреженных графах .
• Алгоритм Витерби решает задачу поиска кратчайшего стохастического пути с дополнительным вероятностным весом на каждом узле.

Дополнительные алгоритмы и связанные с ними оценки можно найти у Черкасского, Голдберга и Радзика (1996) .

Кратчайшие пути из одного источника

Неориентированные графы

Веса	Временная сложность	Автор
$\mathbb {R}$+	O ( V 2 )	Дейкстра 1959 г.
$\mathbb {R}$+	O (( E  +  V ) log  V )	Джонсон 1977 ( двоичная куча )
$\mathbb {R}$+	O ( E  +  V  log  V )	Фредман и Тарьян 1984 ( куча Фибоначчи )
$\mathbb {N}$	О ( Е )	Thorup 1999 (требуется умножение в постоянное время)

Невзвешенные графики

Алгоритм	Временная сложность	Автор
Поиск в ширину	О ( Е + В )

Ориентированные ациклические графы (DAG)

Алгоритм, использующий топологическую сортировку, может решить задачу о кратчайшем пути с одним источником за время Θ( E + V ) в группах DAG с произвольным весом.

Ориентированные графы с неотрицательными весами

Следующая таблица взята из работы Шрийвера (2004) с некоторыми исправлениями и дополнениями.Зеленый фон указывает на асимптотически лучшую границу в таблице; L — максимальная длина (или вес) среди всех ребер, при условии, что веса ребер целые.

Веса	Алгоритм	Временная сложность	Автор
$\mathbb {R}$		$O(V^{2}EL)$	Форд 1956 года
$\mathbb {R}$	Алгоритм Беллмана – Форда	$O(VE)$	Шимбел 1955 г. , Беллман 1958 г. , Мур 1959 г.
$\mathbb {R}$		$O(V^{2}\log {V})$	Данциг 1960 г.
$\mathbb {R}$	Алгоритм Дейкстры со списком	$O(V^{2})$	Лейзорек и др. 1957 г. , Дейкстра 1959 г. , Минти (см. Поллак и Вибенсон 1960 г. ), Whiting & Hillier 1960 г.
$\mathbb {R}$	Алгоритм Дейкстры с двоичной кучей	$O((E+V)\log {V})$	Джонсон 1977 г.
$\mathbb {R}$	Алгоритм Дейкстры с кучей Фибоначчи	$O(E+V\log {V})$	Фредман и Тарьян 1984 , Фредман и Тарьян 1987
$\mathbb {R}$	Квантовый алгоритм Дейкстры со списком смежности	$O({\sqrt {VE}}\log ^{2}{V})$	Дюрр и др. 2006 г.
$\mathbb {N}$	Алгоритм Дайала ( Алгоритм Дейкстры с использованием очереди с L сегментами)	$O(E+LV)$	Циферблат 1969 года
		$O(E\log {\log {L}})$	Джонсон 1981 г. , Карлссон и Поблете 1983 г.
	Алгоритм Габоу	$O(E\log _{E/V}L)$	Старый 1983 , Старый 1985
		$O(E+V{\sqrt {\log {L}}})$	Ахуджа и др. 1990 год
$\mathbb {N}$	Торуп	$O(E+V\log {\log {V}})$	Торуп 2004 г.

Ориентированные графы с произвольными весами без отрицательных циклов

Веса	Алгоритм	Временная сложность	Автор
$\mathbb {R}$		$O(V^{2}EL)$	Форд 1956 года
$\mathbb {R}$	Алгоритм Беллмана – Форда	$O(VE)$	Шимбел 1955 г. , Беллман 1958 г. , Мур 1959 г.
$\mathbb {R}$	Джонсон-Дейкстра с двоичной кучей	$O(VE+V\log V)$	Джонсон 1977 г.
$\mathbb {R}$	Джонсон-Дейкстра с кучей Фибоначчи	$O(VE+V\log V)$	Фредман и Тарьян 1984 г. , Фредман и Тарьян 1987 г. , адаптировано по мотивам Джонсона 1977 г.
$\mathbb {Z}$	Техника Джонсона в применении к алгоритму Дайала	$O(V(E+L))$	Циферблат 1969 года , адаптированный по мотивам Джонсона 1977 года.
$\mathbb {Z}$	Метод внутренней точки с решателем Лапласа	$O(E^{10/7}\log ^{O(1)}V\log ^{O(1)}L)$	Коэн и др. Ошибка harvnb 2017
$\mathbb {Z}$	Метод внутренней точки с $\ell _{p}$ решатель потока	$E^{4/3+o(1)}\log ^{O(1)}L$	Ошибка harvnb Axiotis, Mądry & Vladu 2020
$\mathbb {Z}$	Надежный метод внутренней точки с рисованием	$O((E+V^{3/2})\log ^{O(1)}V\log ^{O(1)}L)$	ван ден Бранд и др. Ошибка harvnb 2020
$\mathbb {Z}$	$\ell _{1}$ метод внутренней точки с динамической структурой данных цикла минимального отношения	$O(E^{1+o(1)}\log L)$	Чен и др. Ошибка harvnb 2022
$\mathbb {Z}$	На основе разложения по малому диаметру	$O(E\log ^{8}V\log L)$	Бернштейн, Нанонгкай и Вульф-Нильсен, 2022 г.
$\mathbb {R}$	Кратчайшие пути с ограничением переходов	$O(EV^{8/9}\log ^{O(1)}V)$	Ошибка Fineman 2023

Ориентированные графы с произвольными весами и отрицательными циклами

Находит отрицательный цикл или вычисляет расстояния до всех вершин.

Веса	Алгоритм	Временная сложность	Автор
$\mathbb {Z}$		$O(E{\sqrt {V}}\log {N})$	Эндрю В. Голдберг

Плоские графы с неотрицательными весами

Веса	Алгоритм	Временная сложность	Автор
$\mathbb {R} _{\geq 0}$		$O(V)$	Хензингер и др. 1997 год

Всепарные кратчайшие пути

Задача о кратчайшем пути для всех пар находит кратчайшие пути между каждой парой вершин v , v' в графе. Задача о кратчайших путях для всех пар для невзвешенных ориентированных графов была предложена Шимбелом (1953) , который заметил, что ее можно решить с помощью линейного числа умножений матриц, что занимает общее время O ( V ⁴ ) .

Неориентированный граф

Веса	Временная сложность	Алгоритм
$\mathbb {R}$+	O ( V 3 )	Алгоритм Флойда – Уоршалла
$\{1,\infty \}$	$O(V^{\omega }\log V)$	Алгоритм Зейделя (ожидаемое время работы)
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log V)^{1/2}})$	Уильямс 2014
$\mathbb {R}$+	O ( EV  log α( E , V ))	Петти и Рамачандран, 2002 г.
$\mathbb {N}$	О ( ЕВ )	Thorup 1999 применяется к каждой вершине (требует умножения в постоянное время).

Ориентированный граф

Веса	Временная сложность	Алгоритм
$\mathbb {R}$ (нет отрицательных циклов)	$O(V^{3})$	Алгоритм Флойда – Уоршалла
$\mathbb {N}$	$O(V^{3}/2^{\Omega (\log V)^{1/2}})$	Уильямс 2014
$\mathbb {R}$ (нет отрицательных циклов)	$O(V^{2.5}\log ^{2}{V})$	Квантовый поиск
$\mathbb {R}$ (нет отрицательных циклов)	О ( EV + V 2  log  V )	Джонсон-Дейкстра
$\mathbb {R}$ (нет отрицательных циклов)	О ( EV + V 2  log log  V )	Петти 2004 г.
$\mathbb {N}$	О ( EV + V 2  log log  V )	Хагеруп 2000

Приложения

Алгоритмы кратчайшего пути применяются для автоматического поиска маршрутов между физическими местоположениями, например, маршруты проезда на картографических веб -сайтах, таких как MapQuest или Google Maps . Для этого приложения доступны быстрые специализированные алгоритмы.

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

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

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

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

Дорожные сети

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

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

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

• ALT ( поиск A* , ориентиры и неравенство треугольника )
• Флаги дуги
• Иерархии сокращения
• Маршрутизация транзитного узла
• Обрезка по охвату
• Маркировка
• Ярлыки концентратора

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

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

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

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

Пути с ограничениями

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

Частичная наблюдаемость

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

Стратегические кратчайшие пути

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

Обнаружение отрицательного цикла

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

• Алгоритм Беллмана – Форда можно использовать для обнаружения отрицательного цикла во времени. $O(|V||E|)$.
• Черкасский и Гольдберг рассмотрим несколько других алгоритмов обнаружения отрицательного цикла.

Общая алгебраическая основа полуколец: проблема алгебраического пути

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

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

Совсем недавно под названием алгебры оценки была разработана еще более общая основа для решения этих (и гораздо менее очевидно связанных с ними проблем) .

Кратчайший путь в стохастических нестационарных сетях

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

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

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

См. также

• Двунаправленный поиск — алгоритм, который находит кратчайший путь между двумя вершинами ориентированного графа.
• Евклидов кратчайший путь
• Проточная сеть
• K маршрутизация по кратчайшему пути
• Умножение матрицы мин-плюс
• Поиск пути
• Соединение по кратчайшему пути
• Дерево кратчайшего пути
• TRILL (Прозрачное соединение множества ссылок)

Ссылки

Библиография

• Ахуджа, Равиндра К.; Мельхорн, Курт; Орлин, Джеймс; Тарьян, Роберт Э. (апрель 1990 г.). «Более быстрые алгоритмы решения задачи поиска кратчайшего пути» (PDF) . Журнал АКМ . 37 (2). АКМ: 213–223. дои : 10.1145/77600.77615 . hdl : 1721.1/47994 . S2CID   5499589 . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Беллман, Ричард (1958). «О проблеме маршрутизации» . Ежеквартальный журнал прикладной математики . 16 : 87–90. дои : 10.1090/qam/102435 . МР   0102435 .
• Бернштейн, Аарон; Нанонгкай, Данупон; Вульф-Нильсен, Кристиан (2022). «Кратчайшие пути с одним источником с отрицательным весом за почти линейное время». 63-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2022 г. IEEE. стр. 600–611. arXiv : 2203.03456 . дои : 10.1109/focs54457.2022.00063 . ISBN  978-1-6654-5519-0 . S2CID   247958461 .
• Черкасский Борис Владимирович; Гольдберг, Эндрю В .; Радзик, Томаш (1996). «Алгоритмы кратчайших путей: теория и экспериментальная оценка» . Математическое программирование . Сер. А. 73 (2): 129–174. дои : 10.1016/0025-5610(95)00021-6 . МР   1392160 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Кратчайшие пути с одним источником и кратчайшие пути для всех пар». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 580–642. ISBN  0-262-03293-7 .
• Данциг, Великобритания (январь 1960 г.). «По кратчайшему маршруту через сеть». Наука управления . 6 (2): 187–190. дои : 10.1287/mnsc.6.2.187 .
• Дейкстра, EW (1959). «Заметка о двух проблемах, связанных с графами». Нумерическая математика . 1 : 269–271. дои : 10.1007/BF01386390 . S2CID   123284777 .
• Форд, ЛР (1956). Теория сетевых потоков (доклад). Санта-Моника, Калифорния: Корпорация RAND. Р-923.
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1984). Кучи Фибоначчи и их использование в усовершенствованных алгоритмах оптимизации сети . 25-й ежегодный симпозиум по основам информатики. ИИЭЭ . стр. 338–346. дои : 10.1109/SFCS.1984.715934 . ISBN  0-8186-0591-Х .
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. дои : 10.1145/28869.28874 . S2CID   7904683 .
• Габоу, Х.Н. (1983). «Алгоритмы масштабирования сетевых задач» (PDF) . Материалы 24-го ежегодного симпозиума по основам информатики (FOCS, 1983) . стр. 248–258. дои : 10.1109/SFCS.1983.68 .
• Габоу, Гарольд Н. (1985). «Алгоритмы масштабирования сетевых задач» . Журнал компьютерных и системных наук . 31 (2): 148–168. дои : 10.1016/0022-0000(85)90039-X . МР   0828519 .
• Хагеруп, Торбен (2000). «Улучшенные кратчайшие пути в оперативной памяти Word» . В Монтанари, Уго; Ролим, Хосе ДП; Вельцль, Эмо (ред.). Материалы 27-го Международного коллоквиума по автоматам, языкам и программированию . стр. 61–72. ISBN  978-3-540-67715-4 .
• Хензингер, Моника Р.; Кляйн, Филип; Рао, Сатиш; Субраманиан, Сайрам (1997). «Более быстрые алгоритмы поиска кратчайшего пути для планарных графов» . Журнал компьютерных и системных наук . 55 (1): 3–23. дои : 10.1006/jcss.1997.1493 .
• Джонсон, Дональд Б. (1977). «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях» . Журнал АКМ . 24 (1): 1–13. дои : 10.1145/321992.321993 . S2CID   207678246 .
• Джонсон, Дональд Б. (декабрь 1981 г.). «Приоритетная очередь, в которой операции инициализации и очереди занимают время O (log log D ) ». Теория математических систем . 15 (1): 295–309. дои : 10.1007/BF01786986 . МР   0683047 . S2CID   35703411 .
• Карлссон, Рольф Г.; Поблете, Патрисио В. (1983). « Алгоритм O ( m log log D ) для поиска кратчайших путей» . Дискретная прикладная математика . 6 (1): 91–93. дои : 10.1016/0166-218X(83)90104-X . МР   0700028 .
• Лейзорек, М.; Грей, РС; Джонсон, А.А.; Ладью, туалет; Микер, СР-младший; Петри, РМ; Зейтц, Р.Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи . Кливленд, Огайо: Технологический институт Кейса.
• Мур, Э.Ф. (1959). «Кратчайший путь через лабиринт». Труды международного симпозиума по теории переключения (Кембридж, Массачусетс, 2–5 апреля 1957 г.) . Кембридж: Издательство Гарвардского университета. стр. 285–292.
• Петти, Сет; Рамачандран, Виджая (2002). «Вычисление кратчайших путей с помощью сравнений и сложений» . Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 267–276 . ISBN  978-0-89871-513-2 .
• Петти, Сет (26 января 2004 г.). «Новый подход к поиску кратчайших путей для всех пар на вещественно-взвешенных графах» . Теоретическая информатика . 312 (1): 47–74. дои : 10.1016/s0304-3975(03)00402-x .
• Поллак, Морис; Вибенсон, Уолтер (март – апрель 1960 г.). «Решение проблемы кратчайшего маршрута — обзор». Опер. Рез . 8 (2): 224–230. дои : 10.1287/опре.8.2.224 . Приписывает алгоритм Дейкстры Минти («частное общение») на стр. 225.
• Шрийвер, Александр (2004). Комбинаторная оптимизация — многогранники и эффективность . Алгоритмы и комбинаторика. Том. 24. Спрингер. т.А, разд.7.5б, с. 103. ИСБН  978-3-540-20456-5 .
• Шимбель, Альфонсо (1953). «Структурные параметры сетей связи». Вестник математической биофизики . 15 (4): 501–507. дои : 10.1007/BF02476438 .
• Шимбель, А. (1955). «Структура в сетях связи». Материалы симпозиума по информационным сетям . Нью-Йорк, штат Нью-Йорк: Политехническое издательство Политехнического института Бруклина. стр. 199–203.
• Торуп, Миккель (1999). «Ненаправленные кратчайшие пути с одним источником и положительными целочисленными весами за линейное время» . Журнал АКМ . 46 (3): 362–394. дои : 10.1145/316542.316548 . S2CID   207654795 .
• Торуп, Миккель (2004). «Очереди с целочисленными приоритетами с уменьшающимся ключом за постоянное время и проблема кратчайших путей из одного источника» . Журнал компьютерных и системных наук . 69 (3): 330–353. дои : 10.1016/j.jcss.2004.04.003 .
• Уайтинг, PD; Хиллиер, Дж. А. (март – июнь 1960 г.). «Метод поиска кратчайшего маршрута через дорожную сеть». Ежеквартальный журнал операционных исследований . 11 (1/2): 37–40. дои : 10.1057/jors.1960.32 .
• Уильямс, Райан (2014). «Более быстрые кратчайшие пути для всех пар за счет сложности схемы». Материалы 46-го ежегодного симпозиума ACM по теории вычислений (STOC '14) . Нью-Йорк: ACM. стр. 664–673. arXiv : 1312.6680 . дои : 10.1145/2591796.2591811 . МР   3238994 .

Дальнейшее чтение

• Алтынташ, Гекхан (2020). Точные решения задач о кратчайшем пути на основе механических аналогий: в связи с лабиринтами . ООО «Амазон Диджитал Сервисез». ISBN  9798655831896 .
• Фриджиони, Д.; Маркетти-Спаккамела, А.; Нанни, У. (1998). «Полностью динамическая задача о кратчайшем пути с одним источником и ограниченным выходом». Учеб. 7-й год. Симпозиум ACM-SIAM. Дискретные алгоритмы . Атланта, Джорджия. стр. 212–221. CiteSeerX   10.1.1.32.9856 .
• Дрейфус, SE (октябрь 1967 г.). Оценка некоторых алгоритмов кратчайшего пути (PDF) (Отчет). Проект Рэнд. ВВС США. РМ-5433-ПР. Архивировано (PDF) из оригинала 17 ноября 2015 г. DTIC AD-661265.