Самый быстрый алгоритм кратчайшего пути - Shortest Path Faster Algorithm

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

Алгоритм

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

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

Ниже представлен псевдокод алгоритма.^[3] Здесь ${ displaystyle Q}$ - очередь кандидатов вершин в порядке очереди, и ${ Displaystyle ш (и, v)}$ это вес края ${ Displaystyle (и, v)}$.

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

 процедура Кратчайший путь-быстрый-алгоритм (грамм, s)  1    за каждая вершина v ≠ s в V(грамм) 2 д (v): = ∞ 3 d (s): = 0 4 нажать s в Q  5    пока Q не пусто делать  6        ты : = опрос Q  7        для каждого край (ты, v) в E(грамм) делать  8            если d (ты) + w (ты, v) v) тогда  9 дн (v): = d (ты) + w (ты, v) 10                если v не в Q тогда 11 толчок v в Q

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

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

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

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

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

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

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

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

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

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

Методы оптимизации

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

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

процедура Small-Label-First (грамм, Q)    если d (назад (Q)) Q)) тогда        u: = выскочить назад Q        толкнуть тебя перед Q

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

процедура Крупная этикетка-последний (грамм, Q)    Икс : = среднее значение d (v) для всех v в Q    пока d (перед (Q)) > Икс        ты : = открыть перед Q        толкать ты к спине Q

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