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

Вычислительная задача теории графов

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

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

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

Определение

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

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

Пусть где - ребро, инцидентное обоим и . Учитывая вещественную весовую функцию и неориентированный (простой) граф , кратчайший путь от до - это путь (где и ), который по всем возможным минимизирует сумму. Когда каждое ребро в графе имеет единичный вес или , это эквивалентно найти путь с наименьшим количеством ребер. ${\displaystyle E=\{e_{i,j}\}}$ ${\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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

Примечания

1. Кормен и др. 2001, с. 655
2. Дюрр, Кристоф; Хейлигман, Марк; Хойер, Питер; Мхалла, Мехди (январь 2006 г.). «Сложность квантовых запросов некоторых задач на графах». SIAM Journal по вычислительной технике . 35 (6): 1310–1328. arXiv : Quant-ph/0401091 . дои : 10.1137/050644719. ISSN  0097-5397. S2CID  14253494.
3. Dial, Роберт Б. (1969). «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]». Коммуникации АКМ . 12 (11): 632–633. дои : 10.1145/363269.363610 . S2CID  6754003.
4. Дюрр, К.; Хойер, П. (18 июля 1996 г.). «Квантовый алгоритм поиска минимума». arXiv : Quant-ph/9607014 .
5. Наеби, Аран; Уильямс, ВВ (22 октября 2014 г.). «Квантовые алгоритмы для решения задач о кратчайших путях в структурированных случаях». arXiv : 1410,6220 [квант-ph].
6. Сандерс, Питер (23 марта 2009 г.). «Быстрое планирование маршрута». Техническое обсуждение Google . Архивировано из оригинала 11 декабря 2021 г.
7. Чен, Дэнни З. (декабрь 1996 г.). «Разработка алгоритмов и программного обеспечения для решения задач геометрического планирования пути». Обзоры вычислительной техники ACM . 28 (4с). Статья 18. doi :10.1145/242224.242246. S2CID  11761485.
8. Авраам, Иттай; Фиат, Амос; Гольдберг, Эндрю В .; Вернек, Ренато Ф. «Размер шоссе, кратчайшие пути и доказуемо эффективные алгоритмы». Симпозиум ACM-SIAM по дискретным алгоритмам, страницы 782–793, 2010 г.
9. Авраам, Иттай; Деллинг, Дэниел; Гольдберг, Эндрю В .; Вернек, Ренато Ф. Research.microsoft.com/pubs/142356/HL-TR.pdf «Алгоритм маркировки на основе узлов для кратчайших путей в дорожных сетях». Симпозиум по экспериментальным алгоритмам, страницы 230–241, 2011 г.
10. Крогер, Мартин (2005). «Кратчайший множественный несвязный путь для анализа запутывания в двумерных и трехмерных полимерных системах». Компьютерная физика. Коммуникации . 168 (3): 209–232. Бибкод : 2005CoPhC.168..209K. дои : 10.1016/j.cpc.2005.01.020.
11. Лозано, Леонардо; Медалья, Андрес Л. (2013). «О точном методе решения задачи о кратчайшем пути с ограничениями». Компьютеры и исследования операций . 40 (1): 378–384. дои : 10.1016/j.cor.2012.07.008.
12. Осанлоу, Кевин; Бурсук, Андрей; Геттье, Кристоф; Казенав, Тристан; Якопен, Эрик (2019). «Оптимальное решение задач планирования пути с ограничениями с помощью сверточных сетей графов и оптимизированного поиска по дереву». Международная конференция IEEE/RSJ по интеллектуальным роботам и системам (IROS) 2019 . стр. 3519–3525. arXiv : 2108.01036 . doi : 10.1109/IROS40897.2019.8968113. ISBN 978-1-7281-4004-9. S2CID  210706773.
13. Бар-Ной, Амоц; Шибер, Барух (1991). «Проблема канадского путешественника». Материалы второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 261–270. CiteSeerX 10.1.1.1088.3015 . 
14. Николова, Евдокия; Каргер, Дэвид Р. «Планирование маршрута в условиях неопределенности: проблема канадских путешественников» (PDF) . Материалы 23-й Национальной конференции по искусственному интеллекту (AAAI) . стр. 969–974. Архивировано (PDF) из оригинала 9 октября 2022 г.
15. Черкасский, Борис В.; Гольдберг, Эндрю В. (1 июня 1999 г.). «Алгоритмы обнаружения отрицательного цикла». Математическое программирование . 85 (2): 277–311. дои : 10.1007/s101070050058. ISSN  1436-4646. S2CID  79739.
16. Пара, Клод (1967). «Sur des алгоритмы для решения проблем пути в конечных графах». В Розентиэле, Пьер (ред.). Théorie des Graphes (journées Internationales d'Etudes) [Теория графов (международный симпозиум)] . Рим (Италия), июль 1966 года. Дюно (Париж); Гордон и Брич (Нью-Йорк). п. 271. ОСЛК  901424694.
17. Дерниам, Жан Клод; Пара, Клод (1971). Problèmes de cheminement dans lesgraphes [ Задачи о путях в графах ]. Дюно (Париж).
18. Барас, Джон; Теодоракопулос, Джордж (4 апреля 2010 г.). Проблемы путей в сетях. Издательство Морган и Клейпул. стр. 9–. ISBN 978-1-59829-924-3.
19. Гондран, Мишель; Мину, Мишель (2008). "Глава 4". Графы, диоиды и полукольца: новые модели и алгоритмы . Springer Science & Business Media. ISBN 978-0-387-75450-5.
20. Пули, Марк; Кохлас, Юрг (2011). «Глава 6. Алгебры оценки для задач пути». Общий вывод: объединяющая теория для автоматизированного рассуждения . Джон Уайли и сыновья. ISBN 978-1-118-01086-0.
21. Луи, Р.П., 1983. Оптимальные пути в графах со стохастическим или многомерным весом. Сообщения ACM, 26 (9), стр. 670–676.
22. Раджаби-Бахабади, Моджтаба; Шариат-Мохаймани, Афшин; Бабаи, Мохсен; Ан, Чан Ук (2015). «Многоцелевой поиск пути в стохастических нестационарных дорожных сетях с использованием генетического алгоритма недоминируемой сортировки». Экспертные системы с приложениями . 42 (12): 5056–5064. дои : 10.1016/j.eswa.2015.02.046.
23. Оля, Мохаммад Хессам (2014). «Нахождение кратчайшего пути в комбинированной экспоненте – длина дуги распределения гамма-вероятности». Международный журнал операционных исследований . 21 (1): 25–37. дои : 10.1504/IJOR.2014.064020.
24. Оля, Мохаммад Хессам (2014). «Применение алгоритма Дейкстры для решения общей задачи о кратчайшем пути с нормальной длиной дуги распределения вероятностей». Международный журнал операционных исследований . 21 (2): 143–154. дои : 10.1504/IJOR.2014.064541.

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

• Ахуджа, Равиндра К.; Мельхорн, Курт; Орлин, Джеймс; Тарьян, Роберт Э. (апрель 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 . doi : 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. MR  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 г.ДТИК АД-661265.