Алгоритм Дейкстров ( / д aɪ к ы т г ə г / Dyke -strəz ) представляет собой алгоритм для нахождения кратчайших путей между узлами в графе , который может представлять собой, например, дорожную сеть . Он был задуман компьютерным ученым Эдсгером В. Дейкстрой в 1956 году и опубликован тремя годами позже. [4] [5] [6]
Класс | Алгоритм поиска Жадный алгоритм Динамическое программирование [1] |
---|---|
Структура данных | График Обычно используется с приоритетной очередью / кучей для оптимизации [2] [3] |
Наихудшая производительность | [3] |
Алгоритм существует во многих вариантах. Исходный алгоритм Дейкстры находил кратчайший путь между двумя заданными узлами [6], но более распространенный вариант фиксирует один узел как «исходный» и находит кратчайшие пути от источника ко всем другим узлам в графе, создавая кратчайший путь дерево .
Для данного исходного узла в графе алгоритм находит кратчайший путь между этим узлом и любым другим. [7] : 196–206 Его также можно использовать для поиска кратчайших путей от одного узла к одному узлу назначения путем остановки алгоритма после определения кратчайшего пути к узлу назначения. Например, если узлы графа представляют города, а затраты на граничные пути представляют собой расстояния между парами городов, соединенных прямой дорогой (для простоты игнорируйте красный свет, знаки остановки, платные дороги и другие препятствия), можно использовать алгоритм Дейкстры. найти кратчайший маршрут между одним городом и всеми другими городами. Широко используемым применением алгоритма кратчайшего пути являются протоколы сетевой маршрутизации , в первую очередь IS-IS (от промежуточной системы к промежуточной системе) и сначала открытый кратчайший путь ( OSPF ). Он также используется в качестве подпрограммы в других алгоритмах, таких как алгоритм Джонсона .
Алгоритм Дейкстры использует метки, которые являются целыми положительными или действительными числами, которые полностью упорядочены . Его можно обобщить для использования любых частично упорядоченных меток при условии, что последующие метки (следующая метка создается при пересечении края) монотонно не убывают. Это обобщение называется общим алгоритмом поиска кратчайшего пути Дейкстры. [8]
Алгоритм Дейкстры использует структуру данных для хранения и запроса частичных решений, отсортированных по расстоянию от начала. В то время как исходный алгоритм использует очередь с минимальным приоритетом и работает во времени (где количество узлов и количество ребер), также может быть реализовано в используя массив. Идея этого алгоритма также дана в Leyzorek et al. 1957 . Fredman & Tarjan 1984 предлагают использовать очередь с минимальным приоритетом кучи Фибоначчи для оптимизации временной сложности выполнения до. Это асимптотически самый быстрый из известных алгоритмов поиска кратчайшего пути с одним источником для произвольных ориентированных графов с неограниченными неотрицательными весами. Однако специализированные случаи (такие как ограниченные / целочисленные веса, ориентированные ациклические графы и т. Д.) Действительно могут быть улучшены, как описано в специализированных вариантах .
В некоторых областях, в частности в области искусственного интеллекта , алгоритм Дейкстры или его вариант известен как поиск по единообразной стоимости и сформулирован как пример более общей идеи поиска по первому наилучшему . [9]
История
Какой самый короткий способ добраться из Роттердама в Гронинген в целом: из заданного города в заданный. Это алгоритм кратчайшего пути , который я разработал примерно за двадцать минут. Однажды утром я ходил по магазинам в Амстердаме со своей молодой невестой, и, уставшие, мы сели на террасе кафе, чтобы выпить чашку кофе, и я просто думал, смогу ли я это сделать, и затем разработал алгоритм кратчайшего пути. . Как я уже сказал, это было двадцатиминутное изобретение. Фактически, он был опубликован в 59-м году, через три года. Публикация по-прежнему читабельна, на самом деле неплохая. Одна из причин, по которой он такой красивый, заключалась в том, что я разработал его без карандаша и бумаги. Позже я узнал, что одно из преимуществ проектирования без карандаша и бумаги состоит в том, что вы почти вынуждены избегать всех сложностей, которых можно избежать. В конце концов, этот алгоритм стал, к моему большому изумлению, одним из краеугольных камней моей славы.
- Эдсгер Дейкстра, в интервью Филиппу Л. Франа, Коммуникации ACM, 2001 [5]
Дейкстра думал о задаче кратчайшего пути, работая в Математическом центре в Амстердаме в 1956 году программистом, чтобы продемонстрировать возможности нового компьютера под названием ARMAC. [10] Его цель состояла в том, чтобы выбрать и проблему, и решение (которое будет создано компьютером), понятные людям, не занимающимся компьютерами. Он разработал алгоритм кратчайшего пути и позже реализовал его для ARMAC для немного упрощенной транспортной карты 64 городов в Нидерландах (64, так что 6 бит будет достаточно для кодирования номера города). [5] Год спустя он столкнулся с другой проблемой инженеров по аппаратному обеспечению, работающих над следующим компьютером института: минимизировать количество проводов, необходимых для соединения контактов на задней панели машины. В качестве решения он заново открыл алгоритм, известный как алгоритм минимального остовного дерева Прима (известный ранее Ярнику , а также вновь открытый Прим ). [11] [12] Дейкстра опубликовал алгоритм в 1959 году, через два года после Прима и через 29 лет после Ярника. [13] [14]
Алгоритм
Пусть узел, с которого мы начинаем, назовем начальным узлом . Пусть расстояние узла Y быть расстояние от исходного узла к Y . Алгоритм Дейкстры назначит некоторые начальные значения расстояний и попытается улучшить их шаг за шагом.
- Отметьте все узлы как непосещенные. Создайте набор всех непосещенных узлов, называемый непосещенным набором .
- Назначьте каждому узлу примерное значение расстояния: установите его равным нулю для нашего начального узла и бесконечности для всех остальных узлов. Установите начальный узел как текущий. [15]
- Для текущего узла рассмотрите всех его непосещенных соседей и вычислите их ориентировочные расстояния через текущий узел. Сравните недавно рассчитанное ориентировочное расстояние с текущим назначенным значением и назначьте меньшее. Например, если текущий узел A отмечен расстоянием 6, а ребро, соединяющее его с соседом B, имеет длину 2, то расстояние до B через A будет 6 + 2 = 8. Если B ранее был отмечен значком расстояние больше 8, измените его на 8. В противном случае будет сохранено текущее значение.
- Когда мы закончим рассмотрение всех непосещенных соседей текущего узла, отметьте текущий узел как посещенный и удалите его из набора непосещенных . Посещенный узел больше никогда не будет проверен.
- Если узел назначения отмечен как посещенный (при планировании маршрута между двумя конкретными узлами) или если наименьшее предварительное расстояние между узлами в непосещаемом наборе равно бесконечности (при планировании полного обхода; возникает, когда нет связи между начальным узлом и оставшиеся непосещенные узлы), затем остановитесь. Алгоритм закончен.
- В противном случае выберите непосещенный узел, отмеченный наименьшим ориентировочным расстоянием, установите его как новый «текущий узел» и вернитесь к шагу 3.
При планировании маршрута на самом деле нет необходимости ждать, пока целевой узел будет "посещен", как указано выше: алгоритм может остановиться, как только целевой узел будет иметь наименьшее предварительное расстояние среди всех "непосещенных" узлов (и, таким образом, может быть выбран в качестве следующий "текущий").
Описание
Предположим, вы хотите найти кратчайший путь между двумя перекрестками на карте города: начальной точкой и конечной точкой . Алгоритм Дейкстры изначально отмечает расстояние (от начальной точки) до каждого другого пересечения на карте бесконечностью . Это сделано не для того, чтобы подразумевать, что существует бесконечное расстояние, а для того, чтобы отметить, что эти перекрестки еще не посещались. В некоторых вариантах этого метода расстояния перекрестков не указываются . Теперь выберите текущее пересечение на каждой итерации. Для первой итерации текущее пересечение будет начальной точкой, а расстояние до него (метка пересечения) будет равно нулю . Для последующих итераций (после первой) текущее пересечение будет ближайшим непосещенным пересечением к начальной точке (это будет легко найти).
От текущего перекрестка обновите расстояние до каждого непосещенного перекрестка, которое напрямую с ним связано. Это делается путем определения суммы расстояния между непосещенным перекрестком и значением текущего перекрестка, а затем перемаркировкой непосещенного перекрестка с этим значением (суммой), если оно меньше текущего значения непосещенного перекрестка. Фактически, перекресток помечается заново, если путь к нему через текущий перекресток короче, чем ранее известные пути. Чтобы облегчить идентификацию кратчайшего пути, карандашом отметьте дорогу стрелкой, указывающей на перемаркированный перекресток, если вы пометили / перемаркировали его, и сотрите все остальные, указывающие на него. После обновления расстояний до каждого соседнего перекрестка отметьте текущий перекресток как посещенный и выберите непосещенный перекресток с минимальным расстоянием (от начальной точки) или самой нижней меткой в качестве текущего перекрестка. Перекрестки, отмеченные как посещенные, помечаются кратчайшим путем от начальной точки до него и не будут повторно посещаться или возвращаться на них.
Продолжайте этот процесс обновления соседних перекрестков кратчайшими расстояниями, отмечая текущий перекресток как посещенный и переходя к ближайшему непосещаемому перекрестку, пока вы не отметите пункт назначения как посещенный. После того, как вы отметили пункт назначения как посещенный (как в случае с любым посещенным перекрестком), вы определили кратчайший путь к нему от начальной точки и можете проследить свой путь назад, следуя стрелкам в обратном направлении . В реализациях алгоритма это обычно делается (после того, как алгоритм достиг целевого узла), следуя за родителями узлов от целевого узла до начального; вот почему мы также отслеживаем родителя каждого узла.
Этот алгоритм не делает попытки прямого «исследования» к месту назначения, как можно было бы ожидать. Скорее, единственное соображение при определении следующего «текущего» перекрестка - это его расстояние от начальной точки. Таким образом, этот алгоритм расширяется наружу от начальной точки, интерактивно рассматривая каждый узел, который находится ближе с точки зрения кратчайшего пути, пока он не достигнет пункта назначения. При таком понимании становится ясно, как алгоритм обязательно находит кратчайший путь. Однако это может также выявить одну из слабых сторон алгоритма: его относительную медлительность в некоторых топологиях.
Псевдокод
В следующем алгоритме псевдокода код u ← вершина в Q с min dist [u] ищет вершину u в множестве вершин Q , имеющий наименьшее dist [ u ] значение. length ( u , v ) возвращает длину ребра, соединяющего (т.е. расстояние между) двумя соседними узлами ты и v . Переменная alt в строке 18 - это длина пути от корневого узла до соседнего узла. v если бы это должно было пройти u . Если этот путь короче текущего кратчайшего пути, записанного для v , этот текущий путь заменяется этим альтернативный путь. В Массив prev заполняется указателем на узел «следующего перехода» на исходном графе, чтобы получить кратчайший путь к источнику.
1 функция Дейкстры ( График , источник ): 2 3 создать набор вершин Q 4 5 для каждой вершины v в Графике : 6 расст [ v ] ← БЕСКОНЕЧНОСТЬ 7 предыдущая [ v ] ← НЕ ОПРЕДЕЛЕНА 8 добавить v в Q 9 dist [ источник ] ← 0 10 11, пока Q не пусто:12 u ← вершина в Q с минимальным расстоянием [u] 13 14 удалить u из Q15 16 для каждого соседа v элемента u : // только v, которые все еще находятся в Q 17 alt ← dist [ u ] + length ( u , v )18, если altv ]: 19 расстояние [ v ] ← alt 20 назад [ v ] ← u21 год22 return dist [], prev []
Если нас интересует только кратчайший путь между вершинами источник и target , мы можем прекратить поиск после строки 15, если u = цель . Теперь мы можем прочитать кратчайший путь из источник для цель обратной итерацией:
1 S ← пустая последовательность2 u ← target 3, если указано prev [ u ] или u = source : // Что-то делать, только если вершина достижима 4, пока u определено: // Построить кратчайший путь со стеком S 5 вставить u в начало S // Помещаем вершину в стек 6 u ← prev [ u ] // Переход от цели к источнику
Теперь последовательность S - список вершин, составляющих один из кратчайших путей из источник для target или пустую последовательность, если путь не существует.
Более общая проблема - найти все кратчайшие пути между источник и target (их может быть несколько одинаковой длины). Тогда вместо того, чтобы хранить только один узел в каждой записи prev [] мы бы сохранили все узлы, удовлетворяющие условию релаксации. Например, если оба г и источник подключиться к цель, и оба они лежат на разных кратчайших путях через target (поскольку стоимость края одинакова в обоих случаях), тогда мы добавим оба г и источник для пред [ цель ] . Когда алгоритм завершится, Структура данных prev [] будет фактически описывать граф, который является подмножеством исходного графа с удаленными ребрами. Его ключевым свойством будет то, что если алгоритм был запущен с некоторым начальным узлом, то каждый путь от этого узла к любому другому узлу в новом графе будет кратчайшим путем между этими узлами в исходном графе и всеми путями этой длины от исходный график будет представлен в новом графике. Затем, чтобы на самом деле найти все эти кратчайшие пути между двумя заданными узлами, мы будем использовать алгоритм поиска пути на новом графе, такой как поиск в глубину .
Использование очереди с приоритетом
Очередь с минимальным приоритетом - это абстрактный тип данных, который обеспечивает 3 основные операции: add_with_priority () , reduce_priority () и extract_min () . Как упоминалось ранее, использование такой структуры данных может сократить время вычислений, чем использование базовой очереди. Примечательно, что куча Фибоначчи ( Fredman & Tarjan 1984 ) или очередь Бродала предлагают оптимальные реализации для этих трех операций. Поскольку алгоритм немного отличается, мы упоминаем его здесь, также в псевдокоде:
1 функция Дейкстры ( График , источник ):2 dist [ source ] ← 0 // Инициализация34 создать очередь с приоритетом вершин Q56 для каждой вершины v в Графике : 7 if v ≠ source 8 dist [ v ] ← INFINITY // Неизвестное расстояние от источника до v 9 prev [ v ] ← UNDEFINED // Предшественник v1011 Q .add_with_priority ( v , dist [ v ])121314, пока Q не пусто: // Основной цикл 15 u ← Q .extract_min () // Удаляем и возвращаем лучшую вершину 16 для каждого соседа v из u : // только v, которые все еще находятся в Q 17 alt ← dist [ u ] + длина ( u , v )18, если altv ]19 dist [ v ] ← alt 20 назад [ v ] ← u 21 Q .decrease_priority ( v , alt )2223 возврат , пред.
Вместо того, чтобы заполнять очередь приоритетов всеми узлами на этапе инициализации, также можно инициализировать ее, чтобы она содержала только источник ; Затем, внутри блока, decrease_priority становится add_with_priority операции , если узел уже не в очереди. [7] : 198if alt < dist[v]
Еще одна альтернатива - безоговорочно добавить узлы в приоритетную очередь и вместо этого после извлечения проверить, что более короткое соединение еще не найдено. Это может быть сделано путем дополнительного извлечения соответствующего приоритета p
из очереди и дальнейшей обработки только внутри цикла. [16]if p == dist[u]
while Q is not empty
Эти альтернативы могут использовать очереди приоритетов, полностью основанные на массивах, без функции уменьшения ключа, которая, как было обнаружено, на практике обеспечивает даже более быстрое время вычислений. Однако для более плотных графиков разница в производительности оказалась меньше. [17]
Доказательство правильности
Доказательство алгоритма Дейкстры строится индукцией по количеству посещенных узлов.
Инвариантная гипотеза : для каждого узла v , dist [v] - кратчайшее расстояние от источник для v при перемещении только через посещенные узлы или бесконечность, если такой путь не существует. (Примечание: мы не предполагаем dist [v] - фактическое кратчайшее расстояние для непосещенных узлов.)
Базовый случай - это когда есть только один посещаемый узел, а именно начальный узел. источник , и в этом случае гипотеза тривиальна .
В противном случае предположите гипотезу для n-1 посещенных узлов. В этом случае мы выбираем ребро ву где у тебя меньше всего dist [u] любых непосещенных узлов и ребра vu такое, что dist [u] = dist [v] + длина [v, u] . dist [u] считается кратчайшим расстоянием от источник для u, потому что если бы был более короткий путь, и если бы w был первым непосещенным узлом на этом пути, тогда согласно исходной гипотезе dist [w] > dist [u], что создает противоречие. Аналогично, если бы был более короткий путь к u без использования непосещенных узлов, и если предпоследний узел на этом пути был w , тогда у нас было бы dist [u] = dist [w] + length [w, u] , тоже противоречие.
После обработки u по- прежнему будет верно, что для каждого непосещенного узла ш , dist [w] будет кратчайшим расстоянием от источник для w, используя только посещенные узлы, потому что если бы был более короткий путь, который не проходит u мы бы нашли его раньше, и если бы был более короткий путь, используя u мы бы обновили его при обработке u .
После посещения всех узлов кратчайший путь от источник к любому узлу v состоит только из посещенных узлов, поэтому dist [v] - кратчайшее расстояние.
Продолжительность
Границы времени работы алгоритма Дейкстры на графе с ребрами E и вершинами V можно выразить как функцию количества ребер, обозначенную, и количество вершин, обозначенное , Используя большой-O обозначения . Сложность связана в основном зависит от структуры данных , используемой для представления набора Q . В дальнейшем верхние границы могут быть упрощены, поскольку является для любого графа, но это упрощение не учитывает тот факт, что в некоторых задачах другие верхние границы может держаться.
Для любой структуры данных для набора вершин Q время выполнения находится в [2]
где а также - сложность операций уменьшения и извлечения минимума в Q соответственно. Простейший вариант алгоритма Дейкстры магазинов множество вершин Q как обычный связанный список или массив, и экстракт-минимум просто линейный поиск через все вершины Q . В этом случае время работы составляет.
Если граф хранится как список смежности, время работы для плотного графа (т. Е. Где ) является
- .
Для разреженных графов , то есть графов с гораздо меньшим, чемрёбер, алгоритм Дейкстры может быть реализован более эффективно, сохраняя граф в форме списков смежности и используя самобалансирующееся двоичное дерево поиска , двоичную кучу , кучу парного соединения или кучу Фибоначчи в качестве очереди с приоритетом для реализации минимально эффективного извлечения. Для эффективного выполнения шагов уменьшения ключа в двоичной куче необходимо использовать вспомогательную структуру данных, которая отображает каждую вершину в ее положение в куче, и поддерживать эту структуру в актуальном состоянии по мере изменения очереди Q приоритетов . С самобалансирующимся двоичным деревом поиска или двоичной кучей алгоритм требует
время в худшем случае (где обозначает двоичный логарифм ); для связных графов эту временную границу можно упростить до. Куча Фибоначчи улучшает это
При использовании двоичных куч средняя временная сложность случая ниже, чем в наихудшем случае: если предположить, что затраты на грани получены независимо от общего распределения вероятностей , ожидаемое количество операций с уменьшением ключа ограничено, что дает общее время работы [7] : 199–200
Практические оптимизации и бесконечные графики
В обычных представлениях алгоритма Дейкстры изначально все узлы помещаются в очередь приоритетов. Однако в этом нет необходимости: алгоритм может начинать с приоритетной очереди, содержащей только один элемент, и вставлять новые элементы по мере их обнаружения (вместо нажатия клавиши уменьшения проверьте, находится ли ключ в очереди; если он есть, уменьшите его ключ, в противном случае вставьте его). [7] : 198 Этот вариант имеет те же границы наихудшего случая, что и общий вариант, но на практике поддерживает очередь с меньшим приоритетом, что ускоряет операции с очередями. [9]
Более того, отсутствие вставки всех узлов в граф позволяет расширить алгоритм для поиска кратчайшего пути от одного источника до ближайшего из набора целевых узлов на бесконечных графах или тех, которые слишком велики для представления в памяти. Результирующий алгоритм называется поиском с равномерной стоимостью (UCS) в литературе по искусственному интеллекту [9] [18] [19] и может быть выражен в псевдокоде как
Процедура uniform_cost_search (график, начало, цель) является узел ← начало стоимость ← 0 frontier ← приоритетная очередь, содержащая только узел исследовано ← пустое множество делать , если граница пуста , то возвращение провал узел ← frontier.pop () если узел является целью, то верните решение explored.add (узел) для каждого из соседей узла n делать, если n не исследуется, то frontier.add ( n )
Сложность этого алгоритма может быть выражена альтернативным способом для очень больших графов: когда C * - это длина кратчайшего пути от начального узла до любого узла, удовлетворяющего предикату "цели", каждое ребро имеет стоимость не менее ε , и число соседей на узел ограниченно Ь , то в худшем случае время и пространство сложность алгоритма является как в O ( б 1 + ⌊ с * / & epsi ; ⌋ ) . [18]
Дальнейшая оптимизация алгоритма Дейкстры для случая единственной цели включает двунаправленные варианты, целенаправленные варианты, такие как алгоритм A * (см. § Связанные проблемы и алгоритмы ), сокращение графа, чтобы определить, какие узлы, вероятно, образуют средний сегмент кратчайших путей (маршрутизация на основе охвата) и иерархическая декомпозиция входного графа, которая сокращает маршрутизацию s - t до подключения s и t к их соответствующим « транзитным узлам » с последующим вычислением кратчайшего пути между этими транзитными узлами с использованием «магистрали». [20] Комбинации таких методов могут потребоваться для оптимального практического выполнения конкретных задач. [21]
Специализированные варианты
Когда веса дуги - маленькие целые числа (ограниченные параметром ), специализированные очереди, использующие этот факт, могут использоваться для ускорения алгоритма Дейкстры. Первым алгоритмом этого типа был алгоритм Dial ( Dial 1969 ) для графов с положительными целочисленными весами ребер, который использует очередь ведра для получения времени выполнения.. Использование дерева Ван Эмде Боаса в качестве очереди с приоритетами усложняет( Ахуджа и др., 1990 ). Еще один интересный вариант, основанный на сочетании новой системы счисления счисления и известной кучи Фибоначчи, работающей во времени.( Ахуджа и др., 1990 ). Наконец, лучшие алгоритмы в этом частном случае следующие. Алгоритм, представленный ( Thorup 2000 ), работает ввремя, и алгоритм, представленный ( Раман 1997 ), работает в время.
Связанные проблемы и алгоритмы
Функциональность оригинального алгоритма Дейкстры может быть расширена с помощью множества модификаций. Например, иногда желательно представить решения, которые не являются оптимальными с математической точки зрения. Чтобы получить ранжированный список неоптимальных решений, сначала вычисляется оптимальное решение. Единственное ребро, появляющееся в оптимальном решении, удаляется из графа, и вычисляется оптимальное решение для этого нового графа. Каждое ребро исходного решения по очереди подавляется и вычисляется новый кратчайший путь. Затем вторичные решения ранжируются и представляются после первого оптимального решения.
Алгоритм Дейкстров, как правило, принцип работы за состоянием канала протоколов маршрутизации , OSPF и IS-IS являются наиболее распространенными из них.
В отличие от алгоритма Дейкстры, алгоритм Беллмана – Форда может использоваться на графах с отрицательными весами ребер, если граф не содержит отрицательных циклов, достижимых из исходной вершины s . Наличие таких циклов означает, что кратчайшего пути нет, поскольку общий вес уменьшается каждый раз при прохождении цикла. (Это утверждение предполагает, что «путь» может повторять вершины. В теории графов это обычно недопустимо. В теоретической информатике это часто допускается.) Можно адаптировать алгоритм Дейкстры для обработки ребер с отрицательным весом, объединив его с алгоритм Беллмана-Форда (для удаления отрицательных краев и обнаружения отрицательных циклов), такой алгоритм называется алгоритмом Джонсона .
Алгоритм A * является обобщением алгоритма Дейкстры , что сокращает размер подграфа , которые должны быть изучены, если имеется дополнительная информация , которая обеспечивает нижнюю границу на «расстояние» до цели. Этот подход можно рассматривать с точки зрения линейного программирования : существует естественная линейная программа для вычисления кратчайших путей , и решения ее двойной линейной программы возможны тогда и только тогда, когда они образуют последовательную эвристику (грубо говоря, поскольку соглашения о знаках различаются с места на место в литературе). Эта выполнимая двойная / согласованная эвристика определяет неотрицательную уменьшенную стоимость, и A *, по сути, выполняет алгоритм Дейкстры с этими уменьшенными затратами. Если дуальный удовлетворяет более слабому условию допустимости , то A * больше похож на алгоритм Беллмана – Форда.
Процесс, лежащий в основе алгоритма Дейкстры, похож на жадный процесс, используемый в алгоритме Прима . Цель Prim - найти минимальное остовное дерево, которое соединяет все узлы в графе; Дейкстра имеет дело только с двумя узлами. Prim не оценивает общий вес пути от начального узла, только отдельные ребра.
Поиск в ширину можно рассматривать как частный случай алгоритма Дейкстры на невзвешенных графах, где приоритетная очередь вырождается в очередь FIFO.
Метод быстрого перехода можно рассматривать как непрерывную версию алгоритма Дейкстры, который вычисляет геодезическое расстояние на треугольной сетке.
Перспектива динамического программирования
С точки зрения динамического программирования алгоритм Дейкстры представляет собой схему последовательного приближения, которая решает функциональное уравнение динамического программирования для задачи кратчайшего пути с помощью метода Достижения . [22] [23] [24]
Фактически, объяснение Дейкстры логики алгоритма [25], а именно
Задача 2. Найти путь минимальной общей длины между двумя заданными узлами. а также .
Мы используем тот факт, что если узел на минимальном пути из к , знание последнего предполагает знание минимального пути из к .
является перефразированием знаменитого принципа оптимальности Беллмана в контексте задачи о кратчайшем пути.
Приложения
Рассчитываются пути с наименьшей стоимостью , например, для прокладки линий электропередач или нефтепроводов. Алгоритм также использовался для расчета оптимальных пешеходных маршрутов на большие расстояния в Эфиопии и сопоставления их с ситуацией на местности. [26]
Смотрите также
- Алгоритм поиска A *
- Алгоритм Беллмана – Форда
- Евклидов кратчайший путь
- Заливка
- Алгоритм Флойда – Уоршолла
- Алгоритм Джонсона
- Проблема самого длинного пути
- Параллельный алгоритм кратчайшего пути для всех пар
Заметки
- ^ Спорный, см. Моше Сниедович (2006). «Пересмотр алгоритма Дейкстры: связь с динамическим программированием» . Управление и кибернетика . 35 : 599–620.и ниже часть .
- ^ а б Кормен и др. 2001 г.
- ^ a b Фредман и Тарджан 1987
- ^ Ричардс, Гамильтон. "Эдсгер Вайбе Дейкстра" . Премия AM Тьюринга . Ассоциация вычислительной техники . Проверено 16 октября 2017 года .
В Математическом центре одним из крупных проектов было создание компьютера ARMAC. На официальном открытии в 1956 году Дейкстра разработал программу для решения проблемы, интересной для нетехнической аудитории: при наличии сети дорог, соединяющих города, какой самый короткий маршрут между двумя обозначенными городами?
- ^ а б в Франа, Фил (август 2010). "Интервью с Эдсгером В. Дейкстрой" . Коммуникации ACM . 53 (8): 41–47. DOI : 10.1145 / 1787234.1787249 .
- ^ а б Дейкстра, EW (1959). «Заметка о двух проблемах, связанных с графиками» (PDF) . Numerische Mathematik . 1 : 269–271. DOI : 10.1007 / BF01386390 . S2CID 123284777 .
- ^ а б в г Мельхорн, Курт ; Сандерс, Питер (2008). «Глава 10. Кратчайшие пути» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Springer. DOI : 10.1007 / 978-3-540-77978-0 . ISBN 978-3-540-77977-3.
- ^ Щесняк, Иренеуш; Яйщик, Анджей; Возна-Щесняк, Божена (2019). «Дженерик Дейкстры для оптических сетей». Журнал оптических коммуникаций и сетей . 11 (11): 568–577. arXiv : 1810.04481 . DOI : 10,1364 / JOCN.11.000568 . S2CID 52958911 .
- ^ а б в Фельнер, Ариэль (2011). Документ с изложением позиции: алгоритм Дейкстры против поиска по единообразной стоимости или аргумент против алгоритма Дейкстры . Proc. 4-й международный симпозиум. по комбинаторному поиску. В задаче поиска маршрута Фельнер обнаружил, что очередь может быть в 500–600 раз меньше, что займет около 40% рабочего времени.
- ^ «АРМАК» . Невоспетые герои в голландской компьютерной истории . 2007. Архивировано из оригинального 13 ноября 2013 года.
- ^ Дейкстра, Эдсгер В., Размышления о «Заметке о двух проблемах, связанных с графами» (PDF)
- ^ Тарджан, Роберт Эндре (1983), Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS_NSF по прикладной математике, 44 , Общество промышленной и прикладной математики, стр. 75.
Третий классический алгоритм минимального остовного дерева был открыт Ярником и повторно открыт Примом и Дикстра; он широко известен как алгоритм Прима.
- ^ Prim, RC (1957). «Сети кратчайших соединений и некоторые обобщения» (PDF) . Технический журнал Bell System . 36 (6): 1389–1401. Bibcode : 1957BSTJ ... 36.1389P . DOI : 10.1002 / j.1538-7305.1957.tb01515.x . Архивировано из оригинального (PDF) 18 июля 2017 года . Проверено 18 июля 2017 года .
- ^ В. Ярник: O jistém problému minimálním [О некоторая минимальная проблема], Práce Moravské Přírodovědecké společnosti, 6, 1930, стр 57-63.. (на чешском языке)
- ^ Гасс, Саул; Фу, Майкл (2013). Гасс, Савл I; Фу, Майкл С. (ред.). «Алгоритм Дейкстры». Энциклопедия исследования операций и науки управления . Springer. 1 . DOI : 10.1007 / 978-1-4419-1153-7 . ISBN 978-1-4419-1137-7 - через Springer Link.
- ^ Обратите внимание, что p
u ] не может удерживаться из-за обновления dist [ v ] ← alt при обновлении очереди. См. Https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key для обсуждения. - ^ Chen, M .; Чоудхури, РА; Рамачандран, V .; Roche, DL; Тонг, Л. (2007). Приоритетные очереди и алгоритм Дейкстры - Технический отчет UTCS TR-07-54 - 12 октября 2007 г. (PDF) . Остин, Техас: Техасский университет в Остине, факультет компьютерных наук.
- ^ а б Рассел, Стюарт ; Норвиг, Питер (2009) [1995]. Искусственный интеллект: современный подход (3-е изд.). Прентис Холл. С. 75, 81. ISBN 978-0-13-604259-4.
- ^ Иногда также поиск с наименьшей стоимостью : Нау, Дана С. (1983). «Экспертные компьютерные системы» (PDF) . Компьютер . IEEE. 16 (2): 63–85. DOI : 10.1109 / mc.1983.1654302 .
- ^ Вагнер, Доротея; Уилхальм, Томас (2007). Ускоренные методы вычисления кратчайшего пути . STACS. С. 23–36.
- ^ Бауэр, Рейнхард; Деллинг, Дэниел; Сандерс, Питер; Шифердекер, Деннис; Шультес, Доминик; Вагнер, Доротея (2010). «Сочетание иерархических и целенаправленных методов ускорения для алгоритма Дейкстры» . J. Экспериментальная алгоритмика . 15 : 2.1. DOI : 10.1145 / 1671970.1671976 . S2CID 1661292 .
- ^ Сниедович, М. (2006). «Новый взгляд на алгоритм Дейкстры: связь с динамическим программированием» (PDF) . Журнал управления и кибернетики . 35 (3): 599–620. Онлайн-версия статьи с интерактивными вычислительными модулями.
- ^ Денардо, Э.В. (2003). Динамическое программирование: модели и приложения . Минеола, Нью-Йорк: Dover Publications . ISBN 978-0-486-42810-9.
- ^ Сниедович, М. (2010). Динамическое программирование: основы и принципы . Фрэнсис и Тейлор . ISBN 978-0-8247-4099-3.
- Перейти ↑ Dijkstra 1959 , p. 270
- ^ Nyssen, J., Tesfaalem Ghebreyohannes, Хайлемари Meaza, Dondeyne, S., 2020. Исследование средневековой африканской карты (Аксум, Эфиопия) - Как исторические карты подходят с рельефом? В: De Ryck, M., Nyssen, J., Van Acker, K., Van Roy, W., Liber Amicorum: Philippe De Maeyer In Kaart. Вахтебеке (Бельгия): University Press: 165-178.
Рекомендации
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Раздел 24.3: алгоритм Дейкстры». Введение в алгоритмы (второе изд.). MIT Press и McGraw – Hill . С. 595–601. ISBN 0-262-03293-7.
- Циферблат, Роберт Б. (1969). «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]» . Коммуникации ACM . 12 (11): 632–633. DOI : 10.1145 / 363269.363610 . S2CID 6754003 .
- Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1984). Куча Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети . 25-й ежегодный симпозиум по основам информатики. IEEE . С. 338–346. DOI : 10.1109 / SFCS.1984.715934 .
- Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». Журнал Ассоциации вычислительной техники . 34 (3): 596–615. DOI : 10.1145 / 28869.28874 . S2CID 7904683 .
- Жан, Ф. Беньямин; Полдень, Чарльз Э. (февраль 1998 г.). «Алгоритмы кратчайшего пути: оценка с использованием реальных дорожных сетей». Транспортная наука . 32 (1): 65–73. DOI : 10,1287 / trsc.32.1.65 . S2CID 14986297 .
- Лейзорек, М .; Серый, RS; Джонсон, AA; Ладью, WC; Микер младший, SR; Петри, РМ; Зейтц, Р. Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи . Кливленд, Огайо: Технологический институт Case.
- Кнут, Д.Е. (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. DOI : 10.1016 / 0020-0190 (77) 90002-3 .
- Ахуджа, Равиндра К .; Мельхорн, Курт; Орлин, Джеймс Б.; Тарджан, Роберт Э. (апрель 1990 г.). «Более быстрые алгоритмы для задачи кратчайшего пути» (PDF) . Журнал ACM . 37 (2): 213–223. DOI : 10.1145 / 77600.77615 . hdl : 1721,1 / 47994 . S2CID 5499589 .
- Раман, Раджив (1997). «Последние результаты по проблеме кратчайших путей из одного источника». Новости SIGACT . 28 (2): 81–87. DOI : 10.1145 / 261342.261352 . S2CID 18031586 .
- Торуп, Миккель (2000). «Очереди приоритета ОЗУ». SIAM Journal on Computing . 30 (1): 86–109. DOI : 10,1137 / S0097539795288246 . S2CID 5221089 .
- Торуп, Миккель (1999). «Ненаправленные кратчайшие пути от одного источника с положительными целыми весами за линейное время» . Журнал ACM . 46 (3): 362–394. DOI : 10.1145 / 316542.316548 . S2CID 207654795 .
Внешние ссылки
- Устное интервью по истории с Эдсгером В. Дейкстра , Институт Чарльза Бэббиджа , Университет Миннесоты, Миннеаполис
- Реализация алгоритма Дейкстры с использованием TDD , Роберт Сесил Мартин , блог The Clean Code
- Пошаговое графическое объяснение алгоритма Дейкстры на примере , Жиль Бертран