Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Кратчайший путь (A, C, E, D, F) между вершинами A и F взвешенного ориентированного графа

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

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

Определение [ править ]

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

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

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

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

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

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

Алгоритмы [ править ]

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

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

Дополнительные алгоритмы и связанные с ними оценки можно найти в Cherkassky, Goldberg & Radzik (1996) .

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

Ненаправленные графики [ править ]

Невзвешенные графики [ править ]

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

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

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

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

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

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

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

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

Ненаправленный граф [ править ]

Направленный график [ править ]

Приложения [ править ]

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

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

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

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

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

Дорожные сети [ править ]

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

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

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

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

Связанные проблемы [ править ]

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

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

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

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

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

Стратегические кратчайшие пути [ править ]

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

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

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

Для данного ориентированного графа ( V , A ) с исходным узлом s , целевым узлом t и стоимостью w ij для каждого ребра ( i , j ) в A рассмотрим программу с переменными x ij

минимизировать при условии и для всех i ,

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

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

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

максимизировать y t - y s при всех ij , y j - y iw ij

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

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

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

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

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

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

Примечания [ править ]

  1. ^ Кормен и др. 2001 , стр. 655
  2. ^ Б циферблат, Роберт Б. (1969), "Алгоритм 360: кратчайший путь лес с топологическим упорядочением [H]" , Сообщениями ACM , 12 (11): 632-633, DOI : 10,1145 / 363269,363610 , S2CID  6754003
  3. Сандерс, Питер (23 марта 2009 г.). «Быстрое планирование маршрута» . Google Tech Talk. Cite journal requires |journal= (help)
  4. Чен, Дэнни З. (декабрь 1996 г.). «Разработка алгоритмов и программного обеспечения для задач геометрического планирования пути». ACM Computing Surveys . 28 (4es). Статья 18. doi : 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 . DOI : 10.1016 / j.cpc.2005.01.020 .
  8. ^ Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993). Сетевые потоки: теория, алгоритмы и приложения . Прентис Холл. ISBN 978-0-13-617549-0.
  9. ^ Пара, Клод (1967), "Sur des алгоритмы для задач de cheminement dans les graphes finis (Об алгоритмах для проблем путей в конечных графах)", в Rosentiehl (ed.), Théorie des graphes (journées internationales d'études) - Теория графов (международный симпозиум) , Рим (Италия), июль 1966 г .: Dunod (Париж) et Gordon and Breach (Нью-Йорк), стр. 271CS1 maint: location (link)
  10. ^ Derniame, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans les graphes (Проблемы пути в графах) , Dunod (Париж)
  11. ^ Барас, Джон; Теодоракопулос, Джордж (4 апреля 2010 г.). Проблемы с путями в сетях . Издатели Morgan & Claypool. С. 9–. ISBN 978-1-59829-924-3.
  12. ^ Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Springer Science & Business Media. Глава 4. ISBN 978-0-387-75450-5.
  13. ^ Пули, Марк; Колас, Юрг (2011). Общий вывод: объединяющая теория для автоматизированных рассуждений . Джон Вили и сыновья. Глава 6. Алгебры оценок для задач о путях. ISBN 978-1-118-01086-0.
  14. ^ Луи, Р.П., 1983. Оптимальные пути в графах со стохастическими или многомерными весами. Сообщения ACM, 26 (9), стр. 670-676.
  15. ^ Раджаби-Bahaabadi, Mojtaba; Шариат-Мохайманы, Афшин; Бабаи, Мохсен; Ан, Чанг Ук (2015). «Многоцелевой поиск пути в стохастических зависящих от времени дорожных сетях с использованием генетического алгоритма недоминируемой сортировки». Экспертные системы с приложениями . 42 (12): 5056–5064. DOI : 10.1016 / j.eswa.2015.02.046 .
  16. ^ Оля, Мохаммад Хессам (2014). «Нахождение кратчайшего пути в комбинированном экспоненциально-гамма-распределении вероятностей по длине дуги». Международный журнал операционных исследований . 21 (1): 25–37. DOI : 10.1504 / IJOR.2014.064020 .
  17. ^ Оля, Мохаммад Хессам (2014). «Применение алгоритма Дейкстры для общей задачи поиска кратчайшего пути с нормальным распределением вероятностей длины дуги». Международный журнал операционных исследований . 21 (2): 143–154. DOI : 10.1504 / IJOR.2014.064541 .

Библиография [ править ]

  • Ахуджа, Равиндра К .; Мельхорн, Курт; Орлин, Джеймс; Тарджан, Роберт Э. (апрель 1990 г.). «Более быстрые алгоритмы решения задачи кратчайшего пути» . Журнал ACM . ACM. 37 (2): 213–223. DOI : 10.1145 / 77600.77615 . hdl : 1721,1 / 47994 . S2CID  5499589 .
  • Беллман, Ричард (1958). «О проблеме маршрутизации» . Квартал прикладной математики . 16 : 87–90. DOI : 10.1090 / QAM / 102435 . Руководство по ремонту  0102435 .
  • Черкасский, Борис В .; Гольдберг, Эндрю В .; Радзик, Томаш (1996). «Алгоритмы кратчайшего пути: теория и экспериментальная оценка» . Математическое программирование . Сер. А. 73 (2): 129–174. DOI : 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. DOI : 10.1287 / mnsc.6.2.187 .
  • Дерниам, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans les graphes (Проблемы пути в графах) , Dunod (Париж)
  • Дейкстра, EW (1959). «Заметка о двух проблемах, связанных с графами». Numerische Mathematik . 1 : 269–271. DOI : 10.1007 / BF01386390 . S2CID  123284777 .
  • Форд, LR (1956). «Теория сетевых потоков» . Rand Corporation. П-923. Cite journal requires |journal= (help)
  • Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (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 .
  • Габоу, HN (1983). «Алгоритмы масштабирования сетевых проблем». Материалы 24-го ежегодного симпозиума по основам информатики (FOCS 1983) (PDF) . С. 248–258. DOI : 10.1109 / SFCS.1983.68 .
  • Габоу, Гарольд Н. (1985). «Алгоритмы масштабирования сетевых проблем». Журнал компьютерных и системных наук . 31 (2): 148–168. DOI : 10.1016 / 0022-0000 (85) 90039-X . Руководство по ремонту  0828519 .
  • Хагеруп, Торбен (2000). Монтанари, Уго; Rolim, José DP; Вельцль, Эмо (ред.). Улучшены кратчайшие пути в ОЗУ Word . Материалы 27-го Международного коллоквиума по автоматам, языкам и программированию . С. 61–72. ISBN 978-3-540-67715-4.
  • Джонсон, Дональд Б. (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 . Руководство по ремонту  0683047 . S2CID  35703411 .
  • Karlsson, Rolf G .; Поблете, Патрисио В. (1983). « Алгоритм O ( m log log D ) для кратчайших путей». Дискретная прикладная математика . 6 (1): 91–93. DOI : 10.1016 / 0166-218X (83) 90104-X . Руководство по ремонту  0700028 .
  • Лейзорек, М .; Серый, RS; Джонсон, AA; Ладью, WC; Meaker, SR, Jr; Петри, РМ; Зейтц, Р. Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи . Кливленд, Огайо: Технологический институт Case.
  • Мур, EF (1959). «Кратчайший путь через лабиринт». Труды Международного симпозиума по теории переключения (Кембридж, Массачусетс, 2–5 апреля 1957 г.) . Кембридж: Издательство Гарвардского университета. С. 285–292.
  • Петти, Сет; Рамачандран, Виджая (2002). Вычисление кратчайших путей со сравнениями и дополнениями . Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . С.  267–276 . ISBN 978-0-89871-513-2.
  • Петти, Сет (26 января 2004 г.). «Новый подход к поиску кратчайших путей для всех пар на вещественно взвешенных графах». Теоретическая информатика . 312 (1): 47–74. DOI : 10.1016 / s0304-3975 (03) 00402-х .
  • Поллак, Морис; Вибенсон, Вальтер (март – апрель 1960 г.). «Решение проблемы кратчайшего пути - обзор». Опер. Res . 8 (2): 224–230. DOI : 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. 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; Хиллер, Дж. А. (март – июнь 1960 г.). «Метод поиска кратчайшего маршрута через дорожную сеть». Ежеквартальные операционные исследования . 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 . Руководство по ремонту  3238994 .

Дальнейшее чтение [ править ]

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