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

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

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

Определение

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

Две вершины смежны, когда они обе инцидентны общему ребру. Путь в неориентированном графе — это последовательность вершин, такая что смежна с для . Такой путь называется путем длины от до . ( Это переменные; их нумерация здесь относится к их положению в последовательности и не должна относиться к какой-либо канонической маркировке вершин.) $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).

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

Шаги трансформации

^[7]

Создайте остаточный график:
- Для каждого ребра (u, v) в исходном графе создадим два ребра в остаточном графе:
  - (u, v) с емкостью c(u, v)
  - (v, u) с емкостью 0
- Остаточный график отображает оставшуюся доступную емкость сети.
Найдите кратчайший путь:
- Используйте алгоритм кратчайшего пути (например, алгоритм Дейкстры, алгоритм Беллмана-Форда), чтобы найти кратчайший путь от исходного узла до приемного узла в остаточном графе.
Увеличьте поток:
- Найдите минимальную пропускную способность по кратчайшему пути.
- Увеличьте поток на краях кратчайшего пути на эту минимальную пропускную способность.
- Уменьшите пропускную способность рёбер в прямом направлении и увеличьте пропускную способность рёбер в обратном направлении.
Обновите остаточный график:
- Обновите остаточный граф на основе дополненного потока.
Повторить:
- Повторяйте шаги 2–4 до тех пор, пока не останется ни одного пути от источника до приемника.

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без отрицательных циклов, задачи поиска кратчайшего пути, которые включают дополнительные ограничения на желаемый путь решения, называются Constrained Shortest Path First и их сложнее решить. Одним из примеров является задача поиска кратчайшего пути с ограничениями ^[15] , которая пытается минимизировать общую стоимость пути, в то же время поддерживая другую метрику ниже заданного порога. Это делает задачу NP-полной (такие задачи не считаются эффективно решаемыми для больших наборов данных, см. задачу P = NP ). Другой пример NP-полной задачи требует включения в путь определенного набора вершин ^[16] , что делает задачу похожей на задачу коммивояжера (TSP). TSP — это задача поиска кратчайшего пути, который проходит через каждую вершину ровно один раз и возвращается в начало. Задача поиска самого длинного пути в графе также является NP-полной.

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

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

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

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

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

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

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

Общая алгебраическая структура полуколец: задача алгебраического пути

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

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

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

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

В реальной жизни транспортная сеть обычно является стохастической и зависящей от времени. Продолжительность поездки по участку дороги зависит от многих факторов, таких как объем трафика (матрица отправления-назначения), дорожные работы, погода, аварии и поломки транспортных средств. Более реалистичной моделью такой дорожной сети является стохастическая зависящая от времени (STD) сеть. ^[25]^[26]

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

Чтобы решить эту проблему, некоторые исследователи используют распределение продолжительности поездки вместо ее ожидаемого значения. Таким образом, они находят распределение вероятностей общей продолжительности поездки, используя различные методы оптимизации, такие как динамическое программирование и алгоритм Дейкстры . ^[27] Эти методы используют стохастическую оптимизацию , в частности, стохастическое динамическое программирование, для поиска кратчайшего пути в сетях с вероятностной длиной дуги. ^[28] Термины надежность времени поездки и изменчивость времени поездки используются как противоположности в литературе по транспортным исследованиям: чем выше изменчивость, тем ниже надежность прогнозов.

Чтобы учесть изменчивость, исследователи предложили два альтернативных определения оптимального пути в условиях неопределенности. Самый надежный путь — это тот, который максимизирует вероятность прибытия вовремя с учетом бюджета времени на поездку. α-надежный путь — это тот, который минимизирует бюджет времени на поездку, необходимый для прибытия вовремя с заданной вероятностью.

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

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

Ссылки

Примечания

^ Задача о кратчайшем пути. doi :10.1007/978-3-031-02574-7.
^ Део, Нарсингх (17 августа 2016 г.). Теория графов с приложениями к инженерии и информатике. Courier Dover Publications. ISBN 978-0-486-80793-5.
^ Кормен и др. 2001, стр. 655
^ Дюрр, Кристоф; Хайлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Квантовая сложность запросов некоторых графовых задач». SIAM Journal on Computing . 35 (6): 1310–1328. arXiv : quant-ph/0401091 . doi : 10.1137/050644719. ISSN 0097-5397. S2CID 14253494.
^ ab Dial, Robert B. (1969). "Алгоритм 360: Лес кратчайших путей с топологическим упорядочением [H]". Сообщения ACM . 12 (11): 632–633. doi : 10.1145/363269.363610 . S2CID 6754003.
^ Кормен, Томас Х. (31 июля 2009 г.). Введение в алгоритмы (3-е изд.). MIT Press. ISBN 9780262533058.{{cite book}}: CS1 maint: date and year (link)
^ Кляйнберг, Джон; Тардос, Ева (2005). Разработка алгоритмов (1-е изд.). Аддисон-Уэсли. ISBN 978-0321295354.
^ Дюрр, К.; Хойер, П. (1996-07-18). «Квантовый алгоритм нахождения минимума». arXiv : quant-ph/9607014 .
^ Наеби, Аран; Уильямс, ВВ (2014-10-22). «Квантовые алгоритмы для задач нахождения кратчайших путей в структурированных случаях». arXiv : 1410.6220 [quant-ph].
^ Сандерс, Питер (23 марта 2009 г.). "Быстрое планирование маршрута". Google Tech Talk . Архивировано из оригинала 2021-12-11.
^ Чен, Дэнни З. (декабрь 1996 г.). «Разработка алгоритмов и программного обеспечения для задач геометрического планирования пути». ACM Computing Surveys . 28 (4es). Статья 18. doi : 10.1145/242224.242246. S2CID 11761485.
^ Абрахам, Иттай; Фиат, Амос; Голдберг, Эндрю В .; Вернек, Ренато Ф. «Измерение шоссе, кратчайшие пути и доказуемо эффективные алгоритмы». Симпозиум ACM-SIAM по дискретным алгоритмам, страницы 782–793, 2010.
^ Абрахам, Иттай; Деллинг, Дэниел; Голдберг, Эндрю В .; Вернек, Ренато Ф. research.microsoft.com/pubs/142356/HL-TR.pdf «Алгоритм маркировки на основе концентратора для кратчайших путей в дорожных сетях». Симпозиум по экспериментальным алгоритмам, страницы 230–241, 2011.
^ Крогер, Мартин (2005). «Кратчайший множественный несвязный путь для анализа запутанности в двумерных и трехмерных полимерных системах». Computer Physics Communications . 168 (3): 209–232. Bibcode : 2005CoPhC.168..209K. doi : 10.1016/j.cpc.2005.01.020.
^ Лосано, Леонардо; Медалья, Андрес Л. (2013). «О точном методе решения задачи поиска кратчайшего пути с ограничениями». Computers & Operations Research . 40 (1): 378–384. doi :10.1016/j.cor.2012.07.008.
^ Осанлу, Кевин; Бурсюк, Андрей; Геттье, Кристоф; Казенав, Тристан; Жакопен, Эрик (2019). «Оптимальное решение задач планирования ограниченного пути с помощью графовых сверточных сетей и оптимизированного поиска по дереву». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS) 2019 г. стр. 3519–3525. arXiv : 2108.01036 . doi :10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID 210706773.
^ Бар-Ной, Амоц; Шибер, Барух (1991). «Проблема канадского путешественника». Труды второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 261–270. CiteSeerX 10.1.1.1088.3015 .
^ Николова, Евдокия; Каргер, Дэвид Р. «Планирование маршрута в условиях неопределенности: проблема канадского путешественника» (PDF) . Труды 23-й Национальной конференции по искусственному интеллекту (AAAI) . стр. 969–974. Архивировано (PDF) из оригинала 2022-10-09.
^ Черкасский, Борис В.; Голдберг, Эндрю В. (1999-06-01). "Алгоритмы обнаружения отрицательного цикла". Математическое программирование . 85 (2): 277–311. doi :10.1007/s101070050058. ISSN 1436-4646. S2CID 79739.
^ Пара, Клод (1967). «Sur des алгоритмы для решения задач о путях в конечных графах». В Розентиэле, Пьер (ред.). Théorie des Graphes (journées Internationales d'Etudes) [Теория графов (международный симпозиум)] . Рим (Италия), июль 1966 года. Дюно (Париж); Гордон и Брич (Нью-Йорк). п. 271. ОСЛК 901424694.
^ Дерниам, Жан Клод; Пара, Клод (1971). Problèmes de cheminement dans lesgraphes [ Задачи о путях в графах ]. Дюно (Париж).
^ Барас, Джон; Теодоракопулос, Джордж (4 апреля 2010 г.). Проблемы путей в сетях. Morgan & Claypool Publishers. стр. 9–. ISBN 978-1-59829-924-3.
^ Gondran, Michel; Minoux, Michel (2008). "глава 4". Графы, диоиды и полукольца: новые модели и алгоритмы . Springer Science & Business Media. ISBN 978-0-387-75450-5.
^ Pouly, Marc; Kohlas, Jürg (2011). "Глава 6. Алгебры оценки для задач пути". Generic Inference: A Unifying Theory for Automated Reasoning . John Wiley & Sons. ISBN 978-1-118-01086-0.
^ Луи, РП, 1983. Оптимальные пути в графах со стохастическими или многомерными весами. Сообщения ACM, 26(9), стр.670-676.
^ Раджаби-Бахабади, Моджтаба; Шариат-Мохаймани, Афшин; Бабаи, Мохсен; Ан, Чанг Вук (2015). «Многоцелевой поиск пути в стохастических дорожных сетях, зависящих от времени, с использованием недоминируемого генетического алгоритма сортировки». Экспертные системы с приложениями . 42 (12): 5056–5064. doi :10.1016/j.eswa.2015.02.046.
^ Оля, Мохаммад Хессам (2014). «Поиск кратчайшего пути в комбинированном экспоненциальном – гамма-распределении вероятности длины дуги». Международный журнал операционных исследований . 21 (1): 25–37. doi :10.1504/IJOR.2014.064020.
^ Оля, Мохаммад Хессам (2014). «Применение алгоритма Дейкстры для общей задачи поиска кратчайшего пути с нормальным распределением вероятностей длины дуги». Международный журнал исследований операций . 21 (2): 143–154. doi :10.1504/IJOR.2014.064541.

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

Ахуджа, Равиндра К.; Мельхорн, Курт; Орлин, Джеймс; Тарьян, Роберт Э. (апрель 1990 г.). «Быстрые алгоритмы для задачи поиска кратчайшего пути» (PDF) . Журнал ACM . 37 (2). ACM: 213–223. doi :10.1145/77600.77615. hdl : 1721.1/47994 . S2CID 5499589. Архивировано (PDF) из оригинала 2022-10-09.
Беллман, Ричард (1958). «О проблеме маршрутизации». Quarterly of Applied Mathematics . 16 : 87–90. doi : 10.1090/qam/102435 . MR 0102435.
Бернстайн, Аарон; Нанонгкай, Данупон; Вульф-Нильсен, Кристиан (2022). «Кратчайшие пути с одним источником с отрицательным весом за почти линейное время». 63-й ежегодный симпозиум IEEE по основам компьютерной науки (FOCS) 2022 г. IEEE. стр. 600–611. arXiv : 2203.03456 . doi :10.1109/focs54457.2022.00063. ISBN 978-1-6654-5519-0. S2CID 247958461.
Черкасский, Борис В.; Голдберг, Эндрю В .; Радзик, Томаш (1996). «Алгоритмы кратчайших путей: теория и экспериментальная оценка». Математическое программирование . Сер. A. 73 (2): 129–174. doi :10.1016/0025-5610(95)00021-6. MR 1392160.
Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001) [1990]. «Кратчайшие пути из одного источника и кратчайшие пути для всех пар». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 580–642. ISBN 0-262-03293-7.
Данциг, ГБ (январь 1960 г.). «О кратчайшем пути через сеть». Наука управления . 6 (2): 187–190. doi :10.1287/mnsc.6.2.187.
Дейкстра, Э. В. (1959). «Заметка о двух проблемах, связанных с графами». Numerische Mathematik . 1 : 269–271. doi :10.1007/BF01386390. S2CID 123284777.
Форд, Л. Р. (1956). Теория сетевых потоков (отчет). Санта-Моника, Калифорния: RAND Corporation. P-923.
Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1984). Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации . 25-й ежегодный симпозиум по основам компьютерной науки. IEEE . стр. 338–346. doi :10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации». Журнал Ассоциации вычислительной техники . 34 (3): 596–615. doi : 10.1145/28869.28874 . S2CID 7904683.
Габов, Х. Н. (1983). "Алгоритмы масштабирования для сетевых задач" (PDF) . Труды 24-го ежегодного симпозиума по основам компьютерной науки (FOCS 1983) . стр. 248–258. doi :10.1109/SFCS.1983.68.
Габов, Гарольд Н. (1985). «Алгоритмы масштабирования для сетевых задач». Журнал компьютерных и системных наук . 31 (2): 148–168. doi : 10.1016/0022-0000(85)90039-X . MR 0828519.
Hagerup, Torben (2000). "Улучшенные кратчайшие пути в слове RAM". В Montanari, Ugo; Rolim, José DP; Welzl, Emo (ред.). Труды 27-го Международного коллоквиума по автоматам, языкам и программированию . стр. 61–72. ISBN 978-3-540-67715-4.
Хензингер, Моника Р.; Кляйн, Филип; Рао, Сатиш; Субраманиан, Сайрам (1997). «Быстрые алгоритмы кратчайшего пути для планарных графов». Журнал компьютерных и системных наук . 55 (1): 3–23. doi : 10.1006/jcss.1997.1493 .
Джонсон, Дональд Б. (1977). «Эффективные алгоритмы для кратчайших путей в разреженных сетях». Журнал ACM . 24 (1): 1–13. doi : 10.1145/321992.321993 . S2CID 207678246.
Джонсон, Дональд Б. (декабрь 1981 г.). «Приоритетная очередь, в которой инициализация и операции очереди занимают $O (log log D)$ времени». Математическая теория систем . 15 (1): 295–309. doi :10.1007/BF01786986. MR 0683047. S2CID 35703411.
Karlsson, Rolf G.; Poblete, Patricio V. (1983). "Алгоритм O(m log log D) для кратчайших путей". Discrete Applied Mathematics . 6 (1): 91–93. doi : 10.1016/0166-218X(83)90104-X . MR 0700028.
Leyzorek, M.; Gray, RS; Johnson, AA; Ladew, WC; Meaker, SR Jr.; Petry, RM; Seitz, RN (1957). Исследование методов моделирования — Первый годовой отчет — 6 июня 1956 г. — 1 июля 1957 г. — Исследование методов моделирования для систем связи . Кливленд, Огайо: Технологический институт Кейса.
Мур, Э. Ф. (1959). «Кратчайший путь через лабиринт». Труды Международного симпозиума по теории переключения (Кембридж, Массачусетс, 2–5 апреля 1957 г.) . Кембридж: Издательство Гарвардского университета. С. 285–292.
Pettie, Seth; Ramachandran, Vijaya (2002). "Вычисление кратчайших путей с помощью сравнений и добавлений". Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 267–276. ISBN 978-0-89871-513-2.
Петти, Сет (26 января 2004 г.). «Новый подход к кратчайшим путям для всех пар на графах с вещественным весом». Теоретическая информатика . 312 (1): 47–74. doi : 10.1016/s0304-3975(03)00402-x .
Поллак, Морис; Вибенсон, Уолтер (март–апрель 1960 г.). «Решение задачи о кратчайшем маршруте — обзор». Oper. Res . 8 (2): 224–230. doi :10.1287/opre.8.2.224. Приписывает алгоритм Дейкстры Минти («частное общение») на стр. 225.
Schrijver, Alexander (2004). Комбинаторная оптимизация — многогранники и эффективность . Алгоритмы и комбинаторика. Т. 24. Springer. т. A, раздел 7.5b, стр. 103. ISBN 978-3-540-20456-5.
Шимбел, Альфонсо (1953). «Структурные параметры сетей связи». Бюллетень математической биофизики . 15 (4): 501–507. doi :10.1007/BF02476438.
Шимбел, А. (1955). «Структура в сетях связи». Труды симпозиума по информационным сетям . Нью-Йорк, Нью-Йорк: Политехническое издательство Политехнического института Бруклина. С. 199–203.
Торуп, Миккель (1999). «Ненаправленные кратчайшие пути с одним источником и положительными целыми весами за линейное время». Журнал ACM . 46 (3): 362–394. doi : 10.1145/316542.316548 . S2CID 207654795.
Торуп, Миккель (2004). «Целочисленные приоритетные очереди с уменьшающимся ключом за постоянное время и проблема кратчайших путей из одного источника». Журнал компьютерных и системных наук . 69 (3): 330–353. doi : 10.1016/j.jcss.2004.04.003 .
Whiting, PD; Hillier, JA (март–июнь 1960 г.). «Метод поиска кратчайшего маршрута через дорожную сеть». Operational Research Quarterly . 11 (1/2): 37–40. doi :10.1057/jors.1960.32.
Уильямс, Райан (2014). «Быстрее всех пар кратчайших путей с помощью сложности схемы». Труды 46-го ежегодного симпозиума ACM по теории вычислений (STOC '14) . Нью-Йорк: ACM. С. 664–673. arXiv : 1312.6680 . doi : 10.1145/2591796.2591811. MR 3238994.

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

Алтынташ, Гёкхан (2020). Точные решения задач на кратчайший путь на основе механических аналогий: в связи с лабиринтами. Amazon Digital Services LLC. ISBN 9798655831896.
Фригиони, Д.; Маркетти-Спаккамела, А.; Нанни, У. (1998). "Полностью динамическая проблема поиска кратчайшего пути с одним источником, ограниченная выходом". Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms . Atlanta, GA. pp. 212–221. CiteSeerX 10.1.1.32.9856 .
Dreyfus, SE (октябрь 1967 г.). Оценка некоторых алгоритмов кратчайшего пути (PDF) (Отчет). Project Rand. ВВС США. RM-5433-PR. Архивировано (PDF) из оригинала 17 ноября 2015 г.DTIC AD-661265.