Задача кратчайшего пути - Shortest path problem

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

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

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

Определение

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

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

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

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

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

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

Алгоритмы

Наиболее важные алгоритмы решения этой проблемы:

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

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

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

Ненаправленные графы

Вес	Сложность времени	Автор
ℝ₊	О(V²)	Дейкстра 1959
ℝ₊	О((E + V) журналV)	Джонсон 1977 (двоичная куча )
ℝ₊	О(E + V журналV)	Фредман и Тарьян 1984 (Куча Фибоначчи )
ℕ	О(E)	Thorup 1999 (требуется постоянное умножение)

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

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

Направленные ациклические графы (DAG)

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

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

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

Вес	Алгоритм	Сложность времени	Автор
ℝ		О(V²EL)	Ford 1956 года
ℝ	Алгоритм Беллмана – Форда	О(VE)	Шимбель 1955, Беллман 1958, Мур 1959
ℝ		О(V² журналV)	Данциг 1960
ℝ	Алгоритм Дейкстры со списком	О(V²)	Leyzorek et al. 1957 г., Дейкстра 1959, Минти (см. Поллак и Вибенсон 1960 ), Уайтинг и Хиллиер 1960
ℝ	Алгоритм Дейкстры с участием двоичная куча	О((E + V) журналV)	Джонсон 1977
ℝ	Алгоритм Дейкстры с участием Куча Фибоначчи	О(E + V журналV)	Фредман и Тарджан 1984, Фредман и Тарьян, 1987 г.
ℕ	Алгоритм набора^[2] (Алгоритм Дейкстры с помощью очередь ведра с участием L ведра)	О(E + LV)	Набери 1969
		О(E журнал журналL)	Джонсон 1981, Карлссон и Поблете, 1983 г.
	Алгоритм Габоу	О(E журнал_E/V L)	Габов 1983, Габов 1985
		О(E + V √журнал L)	Ахуджа и др. 1990 г.
	Thorup	О(E + V журнал журналV)	Thorup 2004

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

Вес	Алгоритм	Сложность времени	Автор
ℝ		О(V²EL)	Ford 1956 года
ℝ	Алгоритм Беллмана – Форда	О(VE)	Шимбель 1955, Беллман 1958, Мур 1959
ℝ	Джонсон-Дейкстра с участием двоичная куча	О(V (E + журналV))	Джонсон 1977
ℝ	Джонсон-Дейкстра с участием Куча Фибоначчи	О(V (E + журналV))	Фредман и Тарьян 1984, Фредман и Тарьян, 1987 г., адаптированный после Джонсон 1977
ℕ	Техника Джонсона применяется к алгоритму Dial^[2]	О(V (E + L))	Набери 1969, адаптированный после Джонсон 1977

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

Кратчайшие пути для всех пар

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

Ненаправленный граф

Вес	Сложность времени	Алгоритм
ℝ₊	$О (V 3)$	Алгоритм Флойда-Уоршолла
${ Displaystyle {1, infty }}$	${ Displaystyle O (V ^ { omega} log V)}$	Алгоритм Зейделя (ожидаемое время работы)
ℕ	${ Displaystyle О (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Уильямс 2014
ℝ₊	$О (Электромобиль журнал α (E, V))$	Петти и Рамачандран 2002
ℕ	$О (Электромобиль)$	Thorup 1999 применяется к каждой вершине (требуется постоянное умножение).

Направленный граф

Вес	Сложность времени	Алгоритм
ℝ (без отрицательных циклов)	$О (V 3)$	Алгоритм Флойда-Уоршолла
ℕ	${ Displaystyle О (V ^ {3} / 2 ^ { Omega ( log n) ^ {1/2}})}$	Уильямс 2014
ℝ (без отрицательных циклов)	$О (Электромобиль + V 2 журнал V)$	Джонсон-Дейкстра
ℝ (без отрицательных циклов)	$О (Электромобиль + V 2 журнал журнал V)$	Петти 2004
ℕ	$О (Электромобиль + V 2 журнал журнал V)$	Hagerup 2000

Приложения

Алгоритмы кратчайшего пути применяются для автоматического поиска направлений между физическими точками, например направления движения на веб-картография такие сайты как MapQuest или Карты Гугл. Для этого приложения доступны быстрые специализированные алгоритмы.^[3]

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

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

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

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

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

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

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

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

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

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

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

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

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

Кратчайший путь с несколькими отключениями ^[7] представляет собой представление примитивной сети путей в рамках Теория репутаций.

В проблема самого широкого пути ищет путь так, чтобы минимальная метка любого ребра была как можно больше.

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

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

Формулировка линейного программирования

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

Для ориентированного графа (V, А) с исходным узлом s, целевой узел т, и стоимость ш_ij для каждого края (я, j) в А, рассмотрим программу с переменными Икс_ij

свести к минимуму

{ displaystyle sum _ {ij in A} w_ {ij} x_ {ij}}

при условии

{ Displaystyle х geq 0}

и для всех я,

{ displaystyle sum _ {j} x_ {ij} - sum _ {j} x_ {ji} = { begin {cases} 1, & { text {if}} i = s; - 1, & { text {if}} i = t; 0, & { text {иначе.}} end {case}}}

Интуиция за этим заключается в том, что ${ displaystyle x_ {ij}}$ - индикаторная переменная, определяющая, является ли край (я, j) является частью кратчайшего пути: 1, если он есть, и 0, если это не так. Мы хотим выбрать набор ребер с минимальным весом при условии, что этот набор образует путь из s к т (представлен ограничением равенства: для всех вершин, кроме s и т количество входящих и исходящих ребер, которые являются частью пути, должно быть одинаковым (т. е. это должен быть путь от s до t).

Этот LP обладает тем особым свойством, что он является целостным; более конкретно, каждый базовое оптимальное решение (если он существует) имеет все переменные, равные 0 или 1, а набор ребер, переменные которых равны 1, образуют s-т погружение. См. Ahuja et al.^[8] для одного доказательства, хотя происхождение этого подхода восходит к середине 20 века.

Двойственным для этой линейной программы является

максимизировать у_т − у_s при условии для всех ij, у_j − у_я ≤ ш_ij

а допустимые двойники соответствуют понятию последовательная эвристика для Алгоритм A * для кратчайших путей. Для любого возможного двойного у то снижение затрат ${ displaystyle w '_ {ij} = w_ {ij} -y_ {j} + y_ {i}}$ неотрицательны и А * по сути работает Алгоритм Дейкстры на эти сниженные затраты.

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

Многие проблемы могут быть сформулированы как форма кратчайшего пути для некоторых подходящих понятий сложения вдоль пути и взятия минимума. Общий подход к ним состоит в том, чтобы рассматривать две операции как операции одного полукольцо. Умножение полукольцом выполняется по пути, а сложение - между путями. Эта общая структура известна как проблема алгебраического пути.^[9]^[10]^[11]

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

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

Кратчайший путь в стохастических сетях, зависящих от времени

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

Несмотря на значительный прогресс, достигнутый в течение последнего десятилетия, остается спорным вопрос, как следует определять и идентифицировать оптимальный путь в стохастических дорожных сетях. Другими словами, не существует однозначного определения оптимального пути в условиях неопределенности. Один из возможных и распространенных ответов на этот вопрос - найти путь с минимальным ожидаемым временем в пути. Основное преимущество использования этого подхода состоит в том, что эффективные алгоритмы кратчайшего пути, введенные для детерминированных сетей, могут быть легко использованы для идентификации пути с минимальным ожидаемым временем прохождения в стохастической сети. Однако результирующий оптимальный путь, определенный с помощью этого подхода, может быть ненадежным, поскольку этот подход не учитывает изменчивость времени в пути. Для решения этой проблемы некоторые исследователи используют распределение времени в пути вместо его ожидаемого значения, поэтому они находят распределение вероятностей общего времени в пути, используя различные методы оптимизации, такие как динамическое программирование и Алгоритм Дейкстры .^[16] Эти методы используют стохастическая оптимизация, а именно стохастическое динамическое программирование для поиска кратчайшего пути в сетях с вероятностной длиной дуги.^[17] Понятие надежности времени в пути используется взаимозаменяемо с изменчивостью времени в пути в литературе по исследованиям транспорта, так что в целом можно сказать, что чем выше изменчивость времени в пути, тем ниже будет надежность, и наоборот.

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

Смотрите также

Двунаправленный поиск, алгоритм, который находит кратчайший путь между двумя вершинами на ориентированном графе
Евклидов кратчайший путь
Поточная сеть
Маршрутизация кратчайшего пути K
Умножение матриц мин-плюс
Найти путь
Кратчайший путь моста
Дерево кратчайшего пути

использованная литература

Заметки

^ Cormen et al. 2001 г., п. 655
^ ^а ^б Наберите, Роберт Б. (1969), «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]», Коммуникации ACM, 12 (11): 632–633, Дои:10.1145/363269.363610
^ Сандерс, Питер (23 марта 2009 г.). «Быстрое планирование маршрута». Google Tech Talk. Цитировать журнал требует | журнал = (Помогите)
^ Чен, Дэнни З. (декабрь 1996 г.). «Разработка алгоритмов и программного обеспечения для задач геометрического планирования пути». Опросы ACM Computing. 28 (4es). Статья 18. Дои:10.1145/242224.242246. S2CID 11761485.
^ Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. «Размер шоссе, кратчайшие пути и доказуемо эффективные алгоритмы». Симпозиум ACM-SIAM по дискретным алгоритмам, страницы 782–793, 2010 г.
^ Авраам, Иттай; Деллинг, Дэниел; Гольдберг, Эндрю В.; Вернек, Ренато Ф. research.microsoft.com/pubs/142356/HL-TR.pdf «Алгоритм маркировки на основе концентраторов для кратчайших путей в дорожных сетях». Симпозиум по экспериментальным алгоритмам, страницы 230–241, 2011 г.
^ Крогер, Мартин (2005). «Кратчайший многократно отключенный путь для анализа сцеплений в двух- и трехмерных полимерных системах». Компьютерная физика Коммуникации. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. Дои:10.1016 / j.cpc.2005.01.020.
^ Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения. Прентис Холл. ISBN 978-0-13-617549-0.
^ Пара, Клод (1967), «Sur des алгоритмы для проблем разрушения в конечных графах (Об алгоритмах для задач путей в конечных графах)», в Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) - Теория графов (международный симпозиум), Рим (Италия), июль 1966 г .: Dunod (Париж) et Gordon and Breach (Нью-Йорк), стр. 271CS1 maint: location (ссылка на сайт)
^ Дерниам, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans les graphes (Проблемы пути в графах), Данод (Париж)
^ Барас, Джон; Теодоракопулос, Джордж (4 апреля 2010 г.). Проблемы с путями в сетях. Издатели Morgan & Claypool. С. 9–. ISBN 978-1-59829-924-3.
^ Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы. Springer Science & Business Media. Глава 4. ISBN 978-0-387-75450-5.
^ Пули, Марк; Колас, Юрг (2011). Общий вывод: объединяющая теория для автоматизированных рассуждений. Джон Вили и сыновья. Глава 6. Алгебры оценок для задач о путях. ISBN 978-1-118-01086-0.
^ Луи Р.П., 1983. Оптимальные пути в графах со стохастическими или многомерными весами. Сообщения ACM, 26 (9), стр. 670-676.
^ Раджаби-Бахаабади, Моджтаба; Шариат-Мохаймани, Афшин; Бабаи, Мохсен; Ан, Чанг Ук (2015). «Многоцелевой поиск пути в стохастических зависящих от времени дорожных сетях с использованием генетического алгоритма недоминируемой сортировки». Экспертные системы с приложениями. 42 (12): 5056–5064. Дои:10.1016 / j.eswa.2015.02.046.
^ Оля, Мохаммад Хессам (2014). «Нахождение кратчайшего пути в комбинированном экспоненциально-гамма-распределении вероятностей длины дуги». Международный журнал операционных исследований. 21 (1): 25–37. Дои:10.1504 / IJOR.2014.064020.
^ Оля, Мохаммад Хессам (2014). «Применение алгоритма Дейкстры для общей задачи поиска кратчайшего пути с нормальной длиной дуги распределения вероятностей». Международный журнал операционных исследований. 21 (2): 143–154. Дои:10.1504 / IJOR.2014.064541.

Список используемой литературы

Ахуджа, Равиндра К .; Мельхорн, Курт; Орлин, Джеймс; Тарджан, Роберт Э. (Апрель 1990 г.). «Более быстрые алгоритмы решения задачи кратчайшего пути». Журнал ACM. ACM. 37 (2): 213–223. Дои:10.1145/77600.77615. HDL:1721.1/47994. S2CID 5499589.
Беллман, Ричард (1958). «О проблеме маршрутизации». Квартал прикладной математики. 16: 87–90. Дои:10.1090 / qam / 102435. Г-Н 0102435.
Черкасский, Борис В .; Гольдберг, Эндрю В.; Радзик, Томаш (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.
Дерниам, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans les graphes (Проблемы пути в графах), Данод (Париж)
Дейкстра, Э. В. (1959). «Заметка о двух проблемах, связанных с графами». Numerische Mathematik. 1: 269–271. Дои:10.1007 / BF01386390. S2CID 123284777.
Форд, Л. Р. (1956). "Теория сетевых потоков". Rand Corporation. П-923. Цитировать журнал требует | журнал = (Помогите)
Фредман, Майкл Лоуренс; Тарджан, Роберт Э. (1984). Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети. 25-й ежегодный симпозиум по основам информатики. IEEE. С. 338–346. Дои:10.1109 / SFCS.1984.715934. ISBN 0-8186-0591-X.
Фредман, Майкл Лоуренс; Тарджан, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». Журнал Ассоциации вычислительной техники. 34 (3): 596–615. Дои:10.1145/28869.28874. S2CID 7904683.
Габоу, Х. Н. (1983). «Алгоритмы масштабирования сетевых проблем». Материалы 24-го ежегодного симпозиума по основам компьютерных наук (FOCS 1983) (PDF). С. 248–258. Дои:10.1109 / SFCS.1983.68.
Габоу, Гарольд Н. (1985). «Алгоритмы масштабирования сетевых проблем». Журнал компьютерных и системных наук. 31 (2): 148–168. Дои:10.1016 / 0022-0000 (85) 90039-Х. Г-Н 0828519.
Hagerup, Торбен (2000). Монтанари, Уго; Rolim, José D. P .; Вельцль, Эмо (ред.). Улучшены кратчайшие пути в ОЗУ Word. Материалы 27-го Международного коллоквиума по автоматам, языкам и программированию. С. 61–72. ISBN 978-3-540-67715-4.
Джонсон, Дональд Б. (1977). «Эффективные алгоритмы поиска кратчайших путей в разреженных сетях». Журнал ACM. 24 (1): 1–13. Дои:10.1145/321992.321993. S2CID 207678246.
Джонсон, Дональд Б. (Декабрь 1981 г.). "Очередь с приоритетом, в которой операции инициализации и очереди занимают $О (журнал журнал D)$ время". Математическая теория систем. 15 (1): 295–309. Дои:10.1007 / BF01786986. Г-Н 0683047. S2CID 35703411.
Karlsson, Rolf G .; Поблете, Патрисио В. (1983). "An $О (м журнал журнал D)$ алгоритм кратчайших путей ». Дискретная прикладная математика. 6 (1): 91–93. Дои:10.1016 / 0166-218X (83) 90104-X. Г-Н 0700028.
Лейзорек, М .; Gray, R. S .; Johnson, A. A .; Ladew, W. C .; Meaker, S. R., Jr .; Петри, Р. М .; Зейтц, Р. Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи. Кливленд, Огайо: Технологический институт Case.
Мур, Э.Ф. (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 / с0304-3975 (03) 00402-х.
Поллак, Морис; Вибенсон, Вальтер (март – апрель 1960 г.). «Решение проблемы кратчайшего пути - обзор». Опер. Res. 8 (2): 224–230. Дои:10.1287 / opre.8.2.224. Приписывает алгоритм Дейкстры Minty («личное общение») на стр. 225.
Шрайвер, Александр (2004). Комбинаторная оптимизация - многогранники и эффективность. Алгоритмы и комбинаторика. 24. Springer. ISBN 978-3-540-20456-5. Здесь: том А, раздел 7.5b, стр. 103
Шимбель, Альфонсо (1953). «Структурные параметры сетей связи». Бюллетень математической биофизики. 15 (4): 501–507. Дои:10.1007 / BF02476438.
Шимбель, А. (1955). Структура в сетях связи. Материалы симпозиума по информационным сетям. Нью-Йорк, штат Нью-Йорк: Политехническая пресса Политехнического института Бруклина. С. 199–203.
Торуп, Миккель (1999). «Ненаправленные кратчайшие пути от одного источника с положительными целыми весами за линейное время». Журнал ACM. 46 (3): 362–394. Дои:10.1145/316542.316548. S2CID 207654795.
Торуп, Миккель (2004). «Очереди с целочисленным приоритетом с ключом уменьшения за постоянное время и проблема кратчайших путей из одного источника». Журнал компьютерных и системных наук. 69 (3): 330–353. Дои:10.1016 / j.jcss.2004.04.003.
Whiting, P.D .; Хиллер, Дж. А. (март – июнь 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.

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

Frigioni, D .; Marchetti-Spaccamela, A .; Нанни, У. (1998). «Задача кратчайшего пути от одного источника с ограниченным полностью динамическим выходом». Proc. 7-й год. ACM-SIAM Symp. Дискретные алгоритмы. Атланта, Джорджия. С. 212–221. CiteSeerX 10.1.1.32.9856.
Дрейфус, С. Э. (октябрь 1967 г.). Оценка некоторых алгоритмов кратчайшего пути (PDF) (Отчет). Project Rand. ВВС США. РМ-5433-ПР. DTIC AD-661265.

[1] Cormen et al. 2001 г., п. 655

[dial69-2] а ^б Наберите, Роберт Б. (1969), «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]», Коммуникации ACM, 12 (11): 632–633, Дои:10.1145/363269.363610

[3] Сандерс, Питер (23 марта 2009 г.). «Быстрое планирование маршрута». Google Tech Talk. Цитировать журнал требует | журнал = (Помогите)

[4] Чен, Дэнни З. (декабрь 1996 г.). «Разработка алгоритмов и программного обеспечения для задач геометрического планирования пути». Опросы ACM Computing. 28 (4es). Статья 18. Дои:10.1145/242224.242246. S2CID 11761485.

[5] Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю В.; Вернек, Ренато Ф. «Размер шоссе, кратчайшие пути и доказуемо эффективные алгоритмы». Симпозиум ACM-SIAM по дискретным алгоритмам, страницы 782–793, 2010 г.

[6] Авраам, Иттай; Деллинг, Дэниел; Гольдберг, Эндрю В.; Вернек, Ренато Ф. research.microsoft.com/pubs/142356/HL-TR.pdf «Алгоритм маркировки на основе концентраторов для кратчайших путей в дорожных сетях». Симпозиум по экспериментальным алгоритмам, страницы 230–241, 2011 г.

[7] Крогер, Мартин (2005). «Кратчайший многократно отключенный путь для анализа сцеплений в двух- и трехмерных полимерных системах». Компьютерная физика Коммуникации. 168 (3): 209–232. Bibcode:2005CoPhC.168..209K. Дои:10.1016 / j.cpc.2005.01.020.

[8] Ахуджа, Равиндра К.; Маньянти, Томас Л.; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения. Прентис Холл. ISBN 978-0-13-617549-0.

[Pair1966-9] Пара, Клод (1967), «Sur des алгоритмы для проблем разрушения в конечных графах (Об алгоритмах для задач путей в конечных графах)», в Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) - Теория графов (международный симпозиум), Рим (Италия), июль 1966 г .: Dunod (Париж) et Gordon and Breach (Нью-Йорк), стр. 271CS1 maint: location (ссылка на сайт)

[10] Дерниам, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans les graphes (Проблемы пути в графах), Данод (Париж)

[BarasTheodorakopoulos2010-11] Барас, Джон; Теодоракопулос, Джордж (4 апреля 2010 г.). Проблемы с путями в сетях. Издатели Morgan & Claypool. С. 9–. ISBN 978-1-59829-924-3.

[GondranMinoux2008-12] Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы. Springer Science & Business Media. Глава 4. ISBN 978-0-387-75450-5.

[PoulyKohlas2012-13] Пули, Марк; Колас, Юрг (2011). Общий вывод: объединяющая теория для автоматизированных рассуждений. Джон Вили и сыновья. Глава 6. Алгебры оценок для задач о путях. ISBN 978-1-118-01086-0.

[14] Луи Р.П., 1983. Оптимальные пути в графах со стохастическими или многомерными весами. Сообщения ACM, 26 (9), стр. 670-676.

[15] Раджаби-Бахаабади, Моджтаба; Шариат-Мохаймани, Афшин; Бабаи, Мохсен; Ан, Чанг Ук (2015). «Многоцелевой поиск пути в стохастических зависящих от времени дорожных сетях с использованием генетического алгоритма недоминируемой сортировки». Экспертные системы с приложениями. 42 (12): 5056–5064. Дои:10.1016 / j.eswa.2015.02.046.

[16] Оля, Мохаммад Хессам (2014). «Нахождение кратчайшего пути в комбинированном экспоненциально-гамма-распределении вероятностей длины дуги». Международный журнал операционных исследований. 21 (1): 25–37. Дои:10.1504 / IJOR.2014.064020.

[17] Оля, Мохаммад Хессам (2014). «Применение алгоритма Дейкстры для общей задачи поиска кратчайшего пути с нормальной длиной дуги распределения вероятностей». Международный журнал операционных исследований. 21 (2): 143–154. Дои:10.1504 / IJOR.2014.064541.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]