Алгоритм Дейкстры

редактировать
Не путать с алгоритмом проектирования Дикстры.

Алгоритм Дейкстры
Dijkstra Animation.gif Алгоритм Дейкстры для поиска кратчайшего пути между a и b. Он выбирает непосещенную вершину с наименьшим расстоянием, вычисляет расстояние через нее до каждого непосещенного соседа и обновляет расстояние до соседа, если оно меньше. Отметьте посещенные (установите красный цвет), когда закончите с соседями.
Класс Алгоритм поиска Жадный алгоритм Динамическое программирование
Структура данных График Обычно используется с приоритетной очередью / кучей для оптимизации
Наихудшая производительность Θ ( | E | + | V | бревно | V | ) {\ Displaystyle \ Theta (| E | + | V | \ log | V |)}

Алгоритм Дейкстров ( / д aɪ к ы т г ə г / Dyke -strəz ) представляет собой алгоритм для нахождения кратчайших путей между узлами в графе, который может представлять собой, например, дорожную сеть. Он был разработан компьютерным ученым Эдсгером В. Дейкстрой в 1956 году и опубликован тремя годами позже.

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

Для данного исходного узла в графе алгоритм находит кратчайший путь между этим узлом и любым другим. Его также можно использовать для поиска кратчайших путей от одного узла к одному узлу назначения путем остановки алгоритма после определения кратчайшего пути к узлу назначения. Например, если узлы графа представляют города, а затраты на граничные пути представляют собой расстояния между парами городов, соединенных прямой дорогой (для простоты игнорируйте красный свет, знаки остановки, платные дороги и другие препятствия), можно использовать алгоритм Дейкстры. найти кратчайший маршрут между одним городом и всеми другими городами. Широко используемым применением алгоритмов кратчайшего пути являются протоколы сетевой маршрутизации, в первую очередь IS-IS (от промежуточной системы к промежуточной системе) и сначала открытый кратчайший путь ( OSPF ). Он также используется в качестве подпрограммы в других алгоритмах, таких как алгоритм Джонсона.

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

Алгоритм Дейкстры использует структуру данных для хранения и запроса частичных решений, отсортированных по расстоянию от начала. Хотя исходный алгоритм использует очередь с минимальным приоритетом и работает во времени (где - количество узлов и - количество ребер), он также может быть реализован с использованием массива. Идея этого алгоритма также дана в Leyzorek et al. 1957. Fredman amp; Tarjan 1984 предлагают использовать очередь с минимальным приоритетом кучи Фибоначчи для оптимизации временной сложности выполнения. Это асимптотически самый быстрый из известных алгоритмов поиска кратчайшего пути с одним источником для произвольных ориентированных графов с неограниченными неотрицательными весами. Однако специализированные случаи (такие как ограниченные / целочисленные веса, ориентированные ациклические графы и т. Д.) Действительно могут быть улучшены, как описано в специализированных вариантах. Кроме того, если предварительная обработка разрешена, такие алгоритмы, как иерархии сжатия, могут быть на семь порядков быстрее. Θ ( ( | V | + | E | ) бревно | V | ) {\ Displaystyle \ Theta ((| V | + | E |) \ log | V |)} | V | {\ displaystyle | V |} | E | {\ displaystyle | E |} Θ ( | V | 2 ) {\ Displaystyle \ Theta (| V | ^ {2})} Θ ( | E | + | V | бревно | V | ) {\ Displaystyle \ Theta (| E | + | V | \ log | V |)}

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

СОДЕРЖАНИЕ

  • 1 История
  • 2 Алгоритм
  • 3 Описание
  • 4 Псевдокод
    • 4.1 Использование очереди приоритетов
  • 5 Доказательство правильности
  • 6 Продолжительность работы
    • 6.1 Практические оптимизации и бесконечные графики
    • 6.2 Специализированные варианты
  • 7 Связанные проблемы и алгоритмы
    • 7.1 Перспектива динамического программирования
  • 8 приложений
  • 9 См. Также
  • 10 заметок
  • 11 Источники
  • 12 Внешние ссылки

История

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

-  Эдсгер Дейкстра, в интервью Филиппу Л. Франа, Коммуникации ACM, 2001 г.

Дейкстра думал о задаче кратчайшего пути, работая в Математическом центре в Амстердаме в 1956 году программистом, чтобы продемонстрировать возможности нового компьютера под названием ARMAC. Его цель состояла в том, чтобы выбрать и проблему, и решение (которое будет создано компьютером), понятные людям, не занимающимся компьютерами. Он разработал алгоритм кратчайшего пути и позже реализовал его для ARMAC для немного упрощенной транспортной карты 64 городов в Нидерландах (64, так что 6 бит будет достаточно для кодирования номера города). Год спустя он столкнулся с другой проблемой инженеров по аппаратному обеспечению, работающих над следующим компьютером института: минимизировать количество проводов, необходимых для соединения контактов на задней панели машины. В качестве решения он заново открыл алгоритм, известный как алгоритм минимального остовного дерева Прима (известный ранее Ярнику, а также вновь открытый Прим ). Дейкстра опубликовал алгоритм в 1959 году, через два года после Прима и через 29 лет после Ярника.

Алгоритм

Иллюстрация алгоритма Дейкстры, находящего путь от начального узла (нижний левый, красный) к целевому узлу (верхний правый, зеленый) в задаче планирования движения робота. Открытые узлы представляют собой «предварительный» набор (он же набор «непосещенных» узлов). Залитые узлы являются посещаемыми, а цвет обозначает расстояние: чем зеленее, тем ближе. Узлы во всех различных направлениях исследуются равномерно, более или менее выглядя как круговой волновой фронт, поскольку алгоритм Дейкстры использует эвристику, идентично равную 0.

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

  1. Отметьте все узлы как непосещенные. Создайте набор всех непосещенных узлов, называемый непосещенным набором.
  2. Назначьте каждому узлу примерное значение расстояния: установите его равным нулю для нашего начального узла и бесконечности для всех остальных узлов. Установите начальный узел как текущий.
  3. Для текущего узла рассмотрите всех его непосещенных соседей и вычислите их ориентировочные расстояния через текущий узел. Сравните недавно рассчитанное ориентировочное расстояние с текущим назначенным значением и назначьте меньшее. Например, если текущий узел A отмечен расстоянием 6, а ребро, соединяющее его с соседом B, имеет длину 2, то расстояние до B через A будет 6 + 2 = 8. Если B ранее был отмечен значком расстояние больше 8, измените его на 8. В противном случае будет сохранено текущее значение.
  4. Когда мы закончим рассмотрение всех непосещенных соседей текущего узла, отметьте текущий узел как посещенный и удалите его из набора непосещенных. Посещенный узел больше никогда не будет проверен.
  5. Если конечный узел отмечен как посещенный (при планировании маршрута между двумя конкретными узлами) или если наименьшее предварительное расстояние между узлами в непосещаемом наборе равно бесконечности (при планировании полного обхода; происходит, когда нет связи между начальным узлом) и оставшиеся непосещенные узлы), затем остановитесь. Алгоритм закончен.
  6. В противном случае выберите непосещенный узел, отмеченный наименьшим ориентировочным расстоянием, установите его как новый «текущий узел» и вернитесь к шагу 3.

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

Описание

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

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

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

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

Этот алгоритм не делает попытки прямого «исследования» к месту назначения, как можно было бы ожидать. Скорее, единственное соображение при определении следующего «текущего» перекрестка - это его расстояние от начальной точки. Таким образом, этот алгоритм расширяется наружу от начальной точки, интерактивно рассматривая каждый узел, который находится ближе с точки зрения кратчайшего пути, пока он не достигнет пункта назначения. При таком понимании становится ясно, как алгоритм обязательно находит кратчайший путь. Однако это может также выявить одну из слабых сторон алгоритма: его относительную медлительность в некоторых топологиях.

Псевдокод

В следующем алгоритме псевдокода dist - это массив, который содержит текущие расстояния от источника до других вершин, то есть dist [ u ] - это текущее расстояние от источника до вершины u. Предыдущий массив содержит указатели на предыдущие-хоп узлы по кратчайшему пути от источника к данной вершине ( что то же самое, это следующий переход на пути от данной вершины к источнику). Код u ← вершина в Q с min dist [u] ищет вершину u в множестве вершин Q, которая имеет наименьшее значение dist [ u ]. length ( u, v) возвращает длину ребра, соединяющего (т.е. расстояние между) двумя соседними узлами u и v. Переменная alt в строке 18 - это длина пути от корневого узла до соседнего узла v, если бы он проходил через u. Если этот путь короче, чем текущий кратчайший путь, записанный для v, этот текущий путь заменяется этим альтернативным путем.

Демонстрация алгоритма Дейкстры, основанного на евклидовом расстоянии. Красные линии - это покрытие кратчайшего пути, т. Е. Соединяющее u и prev [ u ]. Синие линии показывают, где происходит расслабление, т. Е. Соединение v с узлом u в Q, что дает более короткий путь от источника до v.
 1 function Dijkstra(Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: 6 dist[v] ← INFINITY 7 prev[v] ← UNDEFINED 8 add v to Q 9 dist[source] ← 0 10 11 while Q is not empty: 12 u ← vertex in Q with min dist[u] 13 14 remove u from Q 15 16 for each neighbor v of u still in Q: 17 alt ← dist[u] + length(u, v) 18 if alt lt; dist[v]: 19 dist[v] ← alt 20 prev[v] ← u 21 22 return dist[], prev[]

Если нас интересует только кратчайший путь между источником и целью вершин, мы можем завершить поиск после строки 15, если u = target. Теперь мы можем прочитать кратчайший путь от источника к цели путем обратной итерации:

1 S ← empty sequence 2 u ← target 3 if prev[u] is defined or u = source: // Do something only if the vertex is reachable 4 while u is defined: // Construct the shortest path with a stack S 5 insert u at the beginning of S // Push the vertex onto the stack 6 u ← prev[u] // Traverse from target to source

Теперь последовательность S - это список вершин, составляющих один из кратчайших путей от источника к цели, или пустая последовательность, если пути не существует.

Более общая проблема - найти все кратчайшие пути между источником и целью (может быть несколько разных путей одинаковой длины). Тогда вместо того, чтобы хранить только один узел в каждой записи prev [], мы будем хранить все узлы, удовлетворяющие условию релаксации. Например, если и r, и источник подключаются к цели, и оба они лежат на разных кратчайших путях через цель (потому что стоимость ребра одинакова в обоих случаях), то мы бы добавили и r, и источник в prev [ target ]. Когда алгоритм завершится, структура данных prev [] фактически будет описывать граф, который является подмножеством исходного графа с удаленными ребрами. Его ключевым свойством будет то, что если алгоритм был запущен с некоторым начальным узлом, то каждый путь от этого узла к любому другому узлу в новом графе будет кратчайшим путем между этими узлами в исходном графе и всеми путями этой длины от исходный график будет представлен в новом графике. Затем, чтобы на самом деле найти все эти кратчайшие пути между двумя заданными узлами, мы будем использовать алгоритм поиска пути на новом графе, такой как поиск в глубину.

Использование очереди с приоритетом

Очередью мин-приоритетом является абстрактным типом данных, который обеспечивает 3 основные операции: add_with_priority (), decrease_priority () и extract_min (). Как упоминалось ранее, использование такой структуры данных может сократить время вычислений, чем использование базовой очереди. Примечательно, что куча Фибоначчи ( Fredman amp; Tarjan 1984) или очередь Бродала предлагают оптимальные реализации для этих трех операций. Поскольку алгоритм немного отличается, мы упоминаем его здесь, также в псевдокоде:

1 function Dijkstra(Graph, source): 2 dist[source] ← 0 // Initialization 3 4 create vertex priority queue Q 5 6 for each vertex v in Graph: 7 if v ≠ source 8 dist[v] ← INFINITY // Unknown distance from source to v 9 prev[v] ← UNDEFINED // Predecessor of v 10 11 Q.add_with_priority(v, dist[v]) 12 13 14 while Q is not empty: // The main loop 15 u ← Q.extract_min() // Remove and return best vertex 16 for each neighbor v of u: // only v that are still in Q 17 alt ← dist[u] + length(u, v) 18 if alt lt; dist[v] 19 dist[v] ← alt 20 prev[v] ← u 21 Q.decrease_priority(v, alt) 22 23 return dist, prev

Вместо того, чтобы заполнять очередь приоритетов всеми узлами на этапе инициализации, также можно инициализировать ее так, чтобы она содержала только источник ; затем внутри блока операция reduce_priority () становится операцией add_with_priority (), если узел еще не находится в очереди. if alt lt; dist[v]

Еще одна альтернатива - безоговорочно добавить узлы в приоритетную очередь и вместо этого после извлечения проверить, что более короткое соединение еще не найдено. Это может быть сделано путем дополнительного извлечения соответствующего приоритета pиз очереди и дальнейшей обработки только внутри цикла. if p == dist[u]while Q is not empty

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

Доказательство правильности

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

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

Базовый случай - это когда есть только один посещаемый узел, а именно исходный узел- источник, и в этом случае гипотеза тривиальна.

В противном случае предположите гипотезу для n-1 посещенных узлов. В этом случае мы выбираем ребро vu, где u имеет наименьшее dist [u] среди всех непосещенных узлов, так что dist [u] = dist [v] + length [v, u]. dist [u] считается кратчайшим расстоянием от источника до u, потому что если бы был более короткий путь, и если бы w был первым непосещенным узлом на этом пути, то по исходной гипотезе dist [w] gt; dist [u], которая создает противоречие. Точно так же, если бы был более короткий путь к u без использования непосещенных узлов, и если бы предпоследний узел на этом пути был w, тогда у нас было бы dist [u] = dist [w] + length [w, u], также противоречие.

После обработки U она все равно будет верно, что для каждого узла Непосещенных ш, диста [ж] будет кратчайшее расстояние от источника до ж, используя только посещенные узлы, так как если бы более короткий путь, который не проходит U мы имеем нашел его ранее, и если бы был более короткий путь с использованием u, мы бы обновили его при обработке u.

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

Продолжительность

Границы времени работы алгоритма Дейкстры на графе с ребрами Е и вершин V можно выразить как функцию от числа ребер, обозначенных, и числа вершин, обозначаемой, используя большой-O обозначения. Сложность связана в основном зависит от структуры данных, используемой для представления набора Q. В дальнейшем верхние границы могут быть упрощены, потому что это для любого графа, но это упрощение не учитывает тот факт, что в некоторых задачах могут выполняться другие верхние границы. | E | {\ displaystyle | E |} | V | {\ displaystyle | V |} | E | {\ displaystyle | E |} О ( | V | 2 ) {\ Displaystyle O (| V | ^ {2})} | E | {\ displaystyle | E |}

Для любой структуры данных для набора вершин Q время выполнения находится в

Θ ( | E | Т d k + | V | Т е м ) , {\ Displaystyle \ Theta (| E | \ cdot T _ {\ mathrm {dk}} + | V | \ cdot T _ {\ mathrm {em}}),}

где и - сложность операций уменьшения и извлечения минимума в Q соответственно. Простейший вариант алгоритма Дейкстры магазинов множество вершин Q как обычный связанный список или массив, и экстракт-минимум просто линейный поиск через все вершины Q. В этом случае время работы составляет. Т d k {\ Displaystyle Т _ {\ mathrm {dk}}} Т е м {\ displaystyle T _ {\ mathrm {em}}} Θ ( | E | + | V | 2 ) знак равно Θ ( | V | 2 ) {\ Displaystyle \ Theta (| E | + | V | ^ {2}) = \ Theta (| V | ^ {2})}

Если граф хранится как список смежности, время работы для плотного графа (т. Е. Где) равно | E | Θ ( | V | 2 ) {\ displaystyle | E | \ in \ Theta (| V | ^ {2})}

Θ ( ( | V | 2 ) бревно | V | ) {\ Displaystyle \ Theta ((| V | ^ {2}) \ log | V |)}.

Для разреженных графов, то есть графов с гораздо меньшим числом ребер, алгоритм Дейкстры можно реализовать более эффективно, сохранив граф в форме списков смежности и используя самобалансирующееся двоичное дерево поиска, двоичную кучу, кучу сопряжения или кучу Фибоначчи. в качестве очереди с приоритетом для эффективного извлечения минимумов. Для эффективного выполнения шагов уменьшения ключа в двоичной куче необходимо использовать вспомогательную структуру данных, которая отображает каждую вершину в ее положение в куче, и поддерживать эту структуру в актуальном состоянии по мере изменения очереди Q приоритетов. С самобалансирующимся двоичным деревом поиска или двоичной кучей алгоритм требует | V | 2 {\ displaystyle | V | ^ {2}}

Θ ( ( | E | + | V | ) бревно | V | ) {\ Displaystyle \ Theta ((| E | + | V |) \ журнал | V |)}

время в худшем случае (где обозначает двоичный логарифм); для связных графов эту временную границу можно упростить до. Куча Фибоначчи улучшает это бревно {\ displaystyle \ log} бревно 2 {\ displaystyle \ log _ {2}} Θ ( | E | бревно | V | ) {\ Displaystyle \ Theta (| E | \ log | V |)}

Θ ( | E | + | V | бревно | V | ) . {\ Displaystyle \ Theta (| E | + | V | \ log | V |).}

При использовании двоичных куч средняя временная сложность случая ниже, чем для наихудшего случая: если предположить, что затраты на грани получены независимо от общего распределения вероятностей, ожидаемое количество операций с уменьшением ключа ограничено, что дает общее время выполнения Θ ( | V | бревно ( | E | / | V | ) ) {\ Displaystyle \ Theta (| V | \ log (| E | / | V |))}

О ( | E | + | V | бревно | E | | V | бревно | V | ) . {\ displaystyle O \ left (| E | + | V | \ log {\ frac {| E |} {| V |}} \ log | V | \ right).}

Практические оптимизации и бесконечные графики

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

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

procedure uniform_cost_search(Graph, start, goal) is node ← start cost ← 0 frontier ← priority queue containing node only explored ← empty set do if frontier is empty then return failure node ← frontier.pop() if node is goal then return solution explored.add(node) for each of node's neighbors n do if n is not in explored then frontier.add(n)

Сложность этого алгоритма может быть выражена альтернативным способом для очень больших графов: когда C * - это длина кратчайшего пути от начального узла до любого узла, удовлетворяющего предикату "цели", каждое ребро имеет стоимость не менее ε, и количество соседей на узел ограничено b, тогда и временная, и пространственная сложность алгоритма в наихудшем случае находятся в O ( b 1 + ⌊ C * ⁄ ε ⌋).

Дальнейшая оптимизация алгоритма Дейкстры для случая единственной цели включает двунаправленные варианты, целенаправленные варианты, такие как алгоритм A * (см. § Связанные проблемы и алгоритмы), сокращение графа, чтобы определить, какие узлы, вероятно, образуют средний сегмент кратчайших путей (маршрутизация на основе охвата) и иерархическая декомпозиция входного графа, которая сокращает маршрутизацию s - t до подключения s и t к их соответствующим « транзитным узлам » с последующим вычислением кратчайшего пути между этими транзитными узлами с использованием «магистрали». Комбинации таких методов могут потребоваться для оптимального практического выполнения конкретных задач.

Специализированные варианты

Когда веса дуги являются небольшими целыми числами (ограниченными параметром), специализированные очереди, использующие этот факт, могут использоваться для ускорения алгоритма Дейкстры. Первым алгоритмом этого типа был алгоритм Dial ( Dial 1969) для графов с положительными целочисленными весами ребер, который использует очередь ведра для получения времени выполнения. Использование дерева Ван Эмде Боаса в качестве очереди с приоритетами усложняет работу ( Ахуджа и др., 1990). Другой интересный вариант, основанный на комбинации новой системы счисления счисления и хорошо известной кучи Фибоначчи, работающей во времени ( Ахуджа и др., 1990). Наконец, лучшие алгоритмы в этом частном случае следующие. Алгоритм, данный ( Thorup 2000), работает во времени, а алгоритм, данный ( Raman 1997), работает во времени. C {\ displaystyle C} О ( | E | + | V | C ) {\ Displaystyle O (| E | + | V | C)} О ( | E | бревно бревно C ) {\ Displaystyle О (| Е | \ журнал \ журнал C)} О ( | E | + | V | бревно C ) {\ displaystyle O (| E | + | V | {\ sqrt {\ log C}})} О ( | E | бревно бревно | V | ) {\ Displaystyle О (| Е | \ журнал \ журнал | V |)} О ( | E | + | V | мин { ( бревно | V | ) 1 / 3 + ε , ( бревно C ) 1 / 4 + ε } ) {\ Displaystyle О (| Е | + | В | \ мин \ {(\ log | V |) ^ {1/3 + \ varepsilon}, (\ log C) ^ {1/4 + \ varepsilon} \}) }

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

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

Алгоритм Дейкстров, как правило, принцип работы за состоянием канала протоколов маршрутизации, OSPF и IS-IS являются наиболее распространенными из них.

В отличие от алгоритма Дейкстры, алгоритм Беллмана – Форда может использоваться на графах с отрицательными весами ребер, если граф не содержит отрицательных циклов, достижимых из исходной вершины s. Наличие таких циклов означает, что кратчайшего пути нет, поскольку общий вес уменьшается каждый раз при прохождении цикла. (Это утверждение предполагает, что «путь» может повторять вершины. В теории графов это обычно недопустимо. В теоретической информатике это часто допускается.) Можно адаптировать алгоритм Дейкстры для обработки ребер с отрицательным весом, объединив его с алгоритм Беллмана-Форда (для удаления отрицательных краев и обнаружения отрицательных циклов), такой алгоритм называется алгоритмом Джонсона.

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

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

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

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

Перспектива динамического программирования

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

Фактически, объяснение Дейкстры логики алгоритма, а именно

Задача 2. Найти путь минимальной общей длины между двумя заданными узлами и. п {\ displaystyle P} Q {\ displaystyle Q}

Мы используем тот факт, что, если является узлом на минимальном пути от до, знание последнего подразумевает знание минимального пути от до. р {\ displaystyle R} п {\ displaystyle P} Q {\ displaystyle Q} п {\ displaystyle P} р {\ displaystyle R}

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

Приложения

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

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

Примечания

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

внешние ссылки

Последняя правка сделана 2024-01-05 08:27:34
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте