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

Алгоритм поиска по графу

Алгоритм Дейкстры ( / ˈ d aɪ k s t r ə z / DYKE -strəz ) — алгоритм поиска кратчайших путей между узлами во взвешенном графе , который может представлять, например, дорожные сети . Он был задуман ученым-компьютерщиком Эдсгером В. Дейкстрой в 1956 году и опубликован три года спустя. ^{[4] [5] [6]}

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

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

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

Алгоритм Дейкстры использует структуру данных для хранения и запроса частичных решений, отсортированных по расстоянию от начала. Оригинальный алгоритм Дейкстры не использует очередь с минимальным приоритетом и работает во времени (где — количество узлов). ^[10] Идея этого алгоритма также изложена в Leyzorek et al. 1957. Фредман и Тарьян 1984 предлагают использовать очередь с минимальным приоритетом кучи Фибоначчи для оптимизации сложности времени выполнения до . Это асимптотически самый быстрый из известных алгоритмов поиска кратчайшего пути с одним источником для произвольных ориентированных графов с неограниченными неотрицательными весами. Однако специализированные случаи (такие как ограниченные/целочисленные веса, ориентированные ациклические графы и т. д.) действительно могут быть улучшены, как подробно описано в специализированных вариантах. Кроме того, если разрешена предварительная обработка, такие алгоритмы, как сжимающие иерархии , могут работать на семь порядков быстрее. ${\displaystyle \Theta (|V|^{2})}$ ${\displaystyle |V|}$ ${\displaystyle \Theta (|E|+|V|\log |V|)}$

В некоторых областях, в частности в искусственном интеллекте , алгоритм Дейкстры или его вариант известен как поиск с равномерной стоимостью и формулируется как пример более общей идеи поиска по принципу «лучшее по первому требованию» . ^[11]

История

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

-  Эдсгер Дейкстра, в интервью Филипу Л. Фране, Communications of the ACM, 2001 г. ^[5]

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

Алгоритм

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

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

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

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

Описание

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

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

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

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

Псевдокод

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

Демонстрация алгоритма Дейкстры, основанного на евклидовом расстоянии. Красные линии — это покрытие кратчайшего пути, т. е. соединяющее u и prev[ u ]. Синие линии показывают, где происходит расслабление, т. е. соединение v с узлом u в Q , что дает более короткий путь от источника до v .

1 функция Дейкстры ( График , источник ): 2  3 для каждой вершины v в Graph.Vertices : 4 dist[ v ] ← БЕСКОНЕЧНОСТЬ 5 пред[ v ] ← НЕ ОПРЕДЕЛЕНО 6 добавить v к Q 7 dist[ источник ] ← 0 8  9, пока  Q не пуст:10 u ← вершина в Q с min dist[u]11 удалить тебя из Q12 13 для каждого соседа v пользователя u , все еще находящегося в Q :14 alt ← dist[ u ] + Graph.Edges( u , v )15 , если  alt < dist[ v ]:16 dist[ v ] ← alt
17 prev[ v ] ← u1819 возврат расст[], пред[]

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

1 S ← пустая последовательность2 u ← target
3, если prev[ u ] определен или  u = source : // Делать что-то, только если вершина достижима
4, пока  u определена: // Построить кратчайший путь со стеком S
5 вставить u в начало S  // Помещаем вершину в стек
6 u ← prev[ u ] // Переход от цели к источнику

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

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

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

Очередь с минимальным приоритетом — это абстрактный тип данных, который предоставляет 3 основные операции: add_with_priority() , уменьшение_приоритета() и Extract_min() . Как упоминалось ранее, использование такой структуры данных может привести к сокращению времени вычислений, чем использование базовой очереди. Примечательно, что куча Фибоначчи ^[18] или очередь Бродала предлагают оптимальные реализации для этих трех операций. Поскольку алгоритм немного отличается, он упоминается здесь и в псевдокоде:

1 функция Дейкстры ( График , источник ):2 dist[ источник ] ← 0 // Инициализация34 создать очередь приоритетов вершин Q56 для каждой вершины v в Graph.Vertices :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 соседям u
17 alt ← dist[ u ] + Graph.Edges( u , v )18 , если  alt < dist[ v ]:19 dist[ v ] ← alt
20 prev[ v ] ← u
21 Q .decrease_priority( v , alt )2223 возвратное расстояние, предыдущее

Вместо заполнения очереди приоритетов всеми узлами на этапе инициализации также можно инициализировать ее так, чтобы она содержала только источник ; затем внутри блока уменьшение_приоритета() становится операцией add_with_priority() , если узел еще не находится в очереди. ^{[7] : 198}if alt < dist[v]

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

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

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

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

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

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

Далее предположим гипотезу для k-1 посещенных узлов. Далее мы выбираем u в качестве следующего посещенного узла в соответствии с алгоритмом. Мы утверждаем, что это кратчайшее расстояние от источника до u .dist[u]

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

В первом случае пусть w будет первым непосещенным узлом на кратчайшем пути. По гипотезе индукции кратчайший путь от источника до u и w через посещенный узел имеет только стоимость и соответственно. Это означает, что стоимость перехода от источника к u через w имеет стоимость как минимум + минимальную стоимость перехода от w к u . Поскольку стоимость ребер положительна, минимальная стоимость перехода от w к u является положительным числом.dist[u]dist[w]dist[w]

А еще dist[u] < dist[w]потому, что алгоритм выбрал u вместо w .

Теперь мы пришли к противоречию, что dist[u] < dist[w]еще dist[w]+ положительное число < dist[u].

Во втором случае пусть w — предпоследний узел кратчайшего пути. Это значит . Это противоречие, поскольку к моменту посещения w оно должно было установиться не более чем на . dist[w] + Graph.Edges[w,u] < dist[u]dist[u]dist[w] + Graph.Edges[w,u]

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

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

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

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

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

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

${\displaystyle \Theta (|E|\cdot T_{\mathrm {dk} }+|V|\cdot T_{\mathrm {em} }),}$

где и — сложности операций уменьшения ключа и извлечения минимума в Q соответственно. ${\displaystyle T_{\mathrm {dk} }}$ ${\displaystyle T_{\mathrm {em} }}$

Самая простая версия алгоритма Дейкстры сохраняет множество вершин Q как связанный список или массив, а ребра — как список или матрицу смежности . В этом случае extract-minimum — это просто линейный поиск по всем вершинам в Q , поэтому время выполнения равно . ${\displaystyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})}$

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

${\displaystyle \Theta ((|E|+|V|)\log |V|)}$

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

${\displaystyle \Theta (|E|+|V|\log |V|).}$

При использовании двоичных куч средняя временная сложность случая ниже, чем в худшем случае: если предположить, что стоимость ребер рассчитывается независимо от общего распределения вероятностей , ожидаемое количество операций с уменьшением ключа ограничено , что дает общее время выполнения ^{[7]. ] : 199–200} ${\displaystyle \Theta (|V|\log(|E|/|V|))}$

${\displaystyle O\left(|E|+|V|\log {\frac {|E|}{|V|}}\log |V|\right).}$

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

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

Более того, отсутствие вставки всех узлов в граф позволяет расширить алгоритм для поиска кратчайшего пути от одного источника до ближайшего из набора целевых узлов на бесконечных графах или тех, которые слишком велики для представления в памяти. Полученный алгоритм в литературе по искусственному интеллекту называется поиском с равномерной стоимостью (UCS) ^{[11] [21] [22]} и может быть выражен в псевдокоде как

процедура Uniform_cost_search( start ) узел ← начало граница ← приоритетная очередь, содержащая только узел расширенный ← пустой набор сделать  , если граница пуста, а затем  вернуть ошибку узел ← frontier.pop() если узел является целевым состоянием , тогда  верните решение (узел) расширенный.add(узел) для каждого из соседей узла n  сделать  , если  n не находится в расширенном состоянии и не находится на границе, то frontier.add( n ) иначе, если  n находится на границе с более высокой стоимостью заменить существующий узел на n

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Алгоритм поиска A*
• Алгоритм Беллмана – Форда
• Евклидов кратчайший путь
• Алгоритм Флойда – Уоршалла
• Алгоритм Джонсона
• Задача о самом длинном пути
• Параллельный алгоритм поиска кратчайшего пути для всех пар

Примечания

1. Спорно, см. Моше Снедович (2006). «Возвращение к алгоритму Дейкстры: связь с динамическим программированием». Управление и кибернетика . 35 : 599–620.и нижняя часть.
2. Кормен и др. 2001 г.
3. Фредман и Тарьян 1987
4. Ричардс, Гамильтон. «Эдсгер Вайбе Дейкстра». Премия А. М. Тьюринга . Ассоциация вычислительной техники . Проверено 16 октября 2017 г. В Математическом центре крупным проектом было создание компьютера ARMAC. К его официальному открытию в 1956 году Дейкстра разработал программу, призванную решить проблему, интересную нетехнической аудитории: учитывая сеть дорог, соединяющих города, каков кратчайший маршрут между двумя назначенными городами?
5. Франа, Фил (август 2010 г.). «Интервью с Эдсгером В. Дейкстрой». Коммуникации АКМ . 53 (8): 41–47. дои : 10.1145/1787234.1787249.
6. Дейкстра, EW (1959). «Заметка о двух проблемах, связанных с графами». Нумерическая математика . 1 : 269–271. CiteSeerX 10.1.1.165.7577 . дои : 10.1007/BF01386390. S2CID  123284777. 
7. Мельхорн, Курт ; Сандерс, Питер (2008). «Глава 10. Кратчайшие пути» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер. дои : 10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
8. Щесняк, Иренеуш; Яйщик, Анджей; Возна-Щесняк, Божена (2019). «Общий Дейкстра для оптических сетей». Журнал оптических коммуникаций и сетей . 11 (11): 568–577. arXiv : 1810.04481 . дои : 10.1364/JOCN.11.000568. S2CID  52958911.
9. Щесняк, Иренеуш; Возна-Щесняк, Божена (2023), «Общая Дейкстра: корректность и управляемость», NOMS 2023-2023 Симпозиум по сетевым операциям и управлению IEEE/IFIP , стр. 1–7, arXiv : 2204.13547 , doi : 10.1109/NOMS56928.2023.10154 322, ISBN 978-1-6654-7716-1, S2CID  248427020
10. Шрийвер, Александр (2012). «К истории задачи о кратчайшем пути» (PDF) . Документа Математика .
11. Фелнер, Ариэль (2011). Документ с изложением позиции: Алгоритм Дейкстры против поиска равномерной стоимости или аргументы против алгоритма Дейкстры. Учеб. 4-й международный симп. по комбинаторному поиску. Архивировано из оригинала 18 февраля 2020 года . Проверено 12 февраля 2015 г.В задаче поиска маршрута Фелнер обнаружил, что очередь может быть в 500–600 раз меньше, занимая около 40% времени работы.
12. "АРМАК". Невоспетые герои в истории голландской вычислительной техники . 2007. Архивировано из оригинала 13 ноября 2013 года.
13. Дейкстра, Эдсгер В., Размышления о «Заметке о двух проблемах, связанных с графами» (PDF)
14. Тарьян, Роберт Эндре (1983), Структуры данных и сетевые алгоритмы , Серия региональных конференций CBMS_NSF по прикладной математике, том. 44, Общество промышленной и прикладной математики, с. 75. Третий классический алгоритм минимального остовного дерева был открыт Ярником и переоткрыт Примом и Дикстрой; он широко известен как алгоритм Прима.
15. Прим, RC (1957). «Кратчайшие сети связи и некоторые обобщения» (PDF) . Технический журнал Bell System . 36 (6): 1389–1401. Бибкод : 1957BSTJ...36.1389P. doi :10.1002/j.1538-7305.1957.tb01515.x. Архивировано из оригинала (PDF) 18 июля 2017 года . Проверено 18 июля 2017 г.
16. В. Ярник: O jistém problému minimálním [О некоторой минимальной проблеме], Práce Moravské Přírodovědecké Společnosti, 6, 1930, стр. 57–63. (на чешском языке)
17. Гасс, Сол; Фу, Майкл (2013). «Алгоритм Дейкстры». В Гассе, Саул I; Фу, Майкл С. (ред.). Энциклопедия исследований операций и науки управления . Том. 1. Спрингер. дои : 10.1007/978-1-4419-1153-7 . ISBN 978-1-4419-1137-7– через Springer Link.
18. Фредман и Тарьян 1984.
19. Обратите внимание, что p < dist[ u ] никогда не может выполняться из-за обновления dist[ v ] ← alt при обновлении очереди. См. https://cs.stackexchange.com/questions/118388/dijkstra-without-decrease-key для обсуждения.
20. Чен, М.; Чоудхури, РА; Рамачандран, В.; Рош, ДЛ; Тонг, Л. (2007). Очереди с приоритетами и алгоритм Дейкстры - Технический отчет UTCS TR-07-54 - 12 октября 2007 г. (PDF) . Остин, Техас: Техасский университет в Остине, факультет компьютерных наук.
21. Рассел, Стюарт ; Норвиг, Питер (2009) [1995]. Искусственный интеллект: современный подход (3-е изд.). Прентис Холл. стр. 75, 81. ISBN. 978-0-13-604259-4.
22. Иногда также поиск с наименьшими затратами : Нау, Дана С. (1983). «Экспертные компьютерные системы» (PDF) . Компьютер . IEEE. 16 (2): 63–85. дои : 10.1109/mc.1983.1654302. S2CID  7301753.
23. Вагнер, Доротея; Уиллхальм, Томас (2007). Методы ускорения вычислений кратчайшего пути . СТАКС. стр. 23–36.
24. Бауэр, Рейнхард; Деллинг, Дэниел; Сандерс, Питер; Шифердекер, Деннис; Шультес, Доминик; Вагнер, Доротея (2010). «Сочетание иерархических и целенаправленных методов ускорения алгоритма Дейкстры». Дж. Экспериментальная алгоритмика . 15 : 2.1. дои : 10.1145/1671970.1671976. S2CID  1661292.
25. Снедович, М. (2006). «Возвращение к алгоритму Дейкстры: связь с динамическим программированием» (PDF) . Журнал управления и кибернетики . 35 (3): 599–620.Онлайн-версия статьи с интерактивными вычислительными модулями.
26. Денардо, EV (2003). Динамическое программирование: модели и приложения . Минеола, Нью-Йорк: Dover Publications . ISBN 978-0-486-42810-9.
27. Снедович, М. (2010). Динамическое программирование: основы и принципы . Фрэнсис и Тейлор. ISBN 978-0-8247-4099-3.
28. Дейкстра 1959, с. 270

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

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Раздел 24.3: Алгоритм Дейкстры». Введение в алгоритмы (второе изд.). MIT Press и МакГроу-Хилл . стр. 595–601. ISBN 0-262-03293-7.
• Дайал, Роберт Б. (1969). «Алгоритм 360: Лес кратчайшего пути с топологическим упорядочением [H]». Коммуникации АКМ . 12 (11): 632–633. дои : 10.1145/363269.363610 . S2CID  6754003.
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1984). Кучи Фибоначчи и их использование в усовершенствованных алгоритмах оптимизации сети . 25-й ежегодный симпозиум по основам информатики. ИИЭЭ . стр. 338–346. дои : 10.1109/SFCS.1984.715934.
• Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (1987). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети». Журнал Ассоциации вычислительной техники . 34 (3): 596–615. дои : 10.1145/28869.28874 . S2CID  7904683.
• Жан, Ф. Бенджамин; Полдень, Чарльз Э. (февраль 1998 г.). «Алгоритмы кратчайшего пути: оценка с использованием реальных дорожных сетей». Транспортная наука . 32 (1): 65–73. дои : 10.1287/trsc.32.1.65. S2CID  14986297.
• Лейзорек, М.; Грей, РС; Джонсон, А.А.; Ладью, туалет; Микер-младший, старший офицер; Петри, РМ; Зейтц, Р.Н. (1957). Исследование модельных методов - Первый годовой отчет - 6 июня 1956 г. - 1 июля 1957 г. - Исследование модельных методов для систем связи . Кливленд, Огайо: Технологический институт Кейса.
• Кнут, DE (1977). «Обобщение алгоритма Дейкстры». Письма об обработке информации . 6 (1): 1–5. дои : 10.1016/0020-0190(77)90002-3.
• Ахуджа, Равиндра К.; Мельхорн, Курт; Орлин, Джеймс Б.; Тарьян, Роберт Э. (апрель 1990 г.). «Быстрые алгоритмы решения задачи кратчайшего пути» (PDF) . Журнал АКМ . 37 (2): 213–223. дои : 10.1145/77600.77615. hdl : 1721.1/47994 . S2CID  5499589.
• Раман, Раджив (1997). «Недавние результаты по задаче о кратчайших путях из одного источника». Новости СИГАКТ . 28 (2): 81–87. дои : 10.1145/261342.261352 . S2CID  18031586.
• Торуп, Миккель (2000). «Очереди с приоритетом ОЗУ». SIAM Journal по вычислительной технике . 30 (1): 86–109. дои : 10.1137/S0097539795288246. S2CID  5221089.
• Торуп, Миккель (1999). «Ненаправленные кратчайшие пути с одним источником и положительными целочисленными весами за линейное время». Журнал АКМ . 46 (3): 362–394. дои : 10.1145/316542.316548 . S2CID  207654795.

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

• Интервью по устной истории с Эдсгером В. Дейкстрой, Институт Чарльза Бэббиджа , Университет Миннесоты, Миннеаполис
• Реализация алгоритма Дейкстры с использованием TDD, Роберт Сесил Мартин , Блог Clean Code