Самый быстрый алгоритм кратчайшего пути

Кратчайший путь более быстрый алгоритм (SPFA) представляет собой усовершенствование алгоритма Беллмана-Форд , который вычисляет одного источника кратчайшего путь в весовом ориентированном графе. Считается, что алгоритм хорошо работает на случайных разреженных графах и особенно подходит для графов, содержащих ребра с отрицательным весом. ^[1] Однако наихудшая сложность SPFA такая же, как и у Беллмана – Форда, поэтому для графов с неотрицательными весами ребер предпочтительнее алгоритм Дейкстры . Алгоритм SPFA был впервые опубликован Эдвардом Ф. Муром в 1959 году как обобщение поиска в ширину ; ^[2] SPFA - это «алгоритм D» Мура.

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

Учитывая взвешенный ориентированный граф и исходную вершину , алгоритм SPFA находит кратчайший путь от каждой вершины графа. Длина кратчайшего пути от до сохраняется для каждой вершины .${\ Displaystyle G = (V, E)}$${\displaystyle s}$${\displaystyle s}$${\displaystyle v}$${\displaystyle s}$${\displaystyle v}$${\displaystyle d(v)}$${\displaystyle v}$

Основная идея SPFA аналогична алгоритму Беллмана – Форда в том, что каждая вершина используется в качестве кандидата для ослабления смежных вершин. Улучшение по сравнению с последним состоит в том, что вместо того, чтобы пробовать все вершины вслепую, SPFA поддерживает очередь вершин-кандидатов и добавляет вершину в очередь только в том случае, если эта вершина ослаблена. Этот процесс повторяется до тех пор, пока не перестанет расслабляться вершина.

Ниже представлен псевдокод алгоритма. ^[3] Вот очередь вершин-кандидатов «первым пришел - первым обслужен», а это вес ребра . ${\displaystyle Q}$${\displaystyle w(u,v)}$${\displaystyle (u,v)}$

Демонстрация SPFA на основе евклидова расстояния. Красные линии - это покрытие кратчайшего пути (пока наблюдалось). Синие линии указывают, где происходит расслабление, т. Е. Соединение с узлом внутри , что дает более короткий путь от источника до .${\displaystyle v}$${\displaystyle u}$${\displaystyle Q}$${\displaystyle v}$

 процедура Shortest-Path-Faster-Algorithm ( G , s ) 1 для каждой вершины v ≠ s в V ( G ) 2 d ( v ): = ∞ 3 д ( с ): = 0 4 вставьте s в Q 5, пока  Q не пусто do 6 u  : = опрос Q 7 для каждого ребра ( u , v ) в E ( G ) do 8, если d ( u ) + w ( u , v ) <d ( v ), то 9 d ( v ): = d ( u ) + w ( u , v ) 10, если  v не находится в Q,  тогда 11 вставьте v в Q

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

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

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

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

Доказательство : мы хотим показать, что если для любых двух вершин и в то время, когда условие проверяется, находится в очереди. Мы делаем это индукцией по количеству уже выполненных итераций цикла. Прежде всего отметим, что это определенно выполняется до входа в цикл: если , то релаксация невозможна; релаксация возможна из , и она добавляется в очередь непосредственно перед входом в цикл while. Теперь посмотрим, что происходит внутри цикла. Вершина выталкивается и используется для ослабления всех своих соседей, если это возможно. Следовательно, сразу после этой итерации цикла больше не может быть расслаблений (и он больше не должен находиться в очереди). Однако релаксация${\displaystyle dist[w]>dist[u]+wt(u,w)}$${\displaystyle u}$${\displaystyle w}$${\displaystyle u}$${\displaystyle u\not =v}$${\displaystyle u=v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle x}$может привести к тому, что некоторые другие вершины станут способными вызывать релаксацию. Если есть такие, которые до текущей итерации цикла, то уже находятся в очереди. Если это условие становится истинным во время текущей итерации цикла, то либо увеличивается, что невозможно, либо уменьшается, что означает, что это было ослаблено. Но после того , как он расслаблен, он добавляется в очередь, если ее еще нет.${\displaystyle dist[x]>dist[w]+wt(w,x)}$${\displaystyle w}$${\displaystyle dist[x]}$${\displaystyle dist[w]}$${\displaystyle w}$${\displaystyle w}$

Следствие : алгоритм завершается тогда и только тогда, когда дальнейшие ослабления невозможны.

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

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

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

Наихудшее время работы алгоритма такое же, как у стандартного алгоритма Беллмана-Форда . ^[1] Эксперименты показывают, что среднее время работы составляет , и это действительно так для случайных графов, но можно построить разреженные графы, где SPFA работает во времени, как обычный алгоритм Беллмана-Форда. ^[5]${\displaystyle O(|V|\cdot |E|)}$${\displaystyle O(|E|)}$${\displaystyle \Omega (|V|^{2})}$

Методы оптимизации [ править ]

Производительность алгоритма в значительной степени определяется порядком, в котором вершины-кандидаты используются для ослабления других вершин. Фактически, если это очередь с приоритетом, то алгоритм в значительной степени напоминает алгоритм Дейкстры. Однако, поскольку очередь с приоритетом здесь не используется, иногда используются два метода для улучшения качества очереди, что, в свою очередь, улучшает производительность в среднем случае (но не в худшем случае). Оба метода изменяют порядок элементов таким образом, чтобы в первую очередь обрабатывались вершины, расположенные ближе к источнику. Следовательно, при реализации этих методов больше не используется очередь «первым пришел - первым вышел», а скорее обычный двусвязный список или двусторонняя очередь.${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$

Технология Small Label First ( SLF ). В строке 11 вместо того, чтобы всегда помещать вершину в конец очереди, мы сравниваем ее и вставляем в начало очереди, если она меньше. Псевдокод для этой техники (после нажатия до конца очереди в строке 11):${\displaystyle v}$${\displaystyle d(v)}$${\displaystyle d{\big (}{\text{front}}(Q){\big )}}$${\displaystyle v}$${\displaystyle d(v)}$${\displaystyle v}$

процедура Small-Label-First ( G , Q ), если d (back ( Q )) <d (front ( Q )), то u: = вытолкнуть заднюю часть Q, протолкнуть u перед Q

Технология Large Label Last ( LLL ). После строки 11 мы обновляем очередь так, чтобы первый элемент был меньше среднего, а любой элемент больше среднего перемещался в конец очереди. Псевдокод:

процедура Large-Label-Last ( G , Q ) x  : = среднее значение d ( v ) для всех v в Q, в  то время как d (front ( Q ))> x  u  : = вытолкнуть перед Q толкнуть u в заднюю часть Q

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