Самый быстрый алгоритм кратчайшего пути - 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 w(u,v)}$ это вес края ${\displaystyle (u,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 u\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[w]}$ уменьшилось, подразумевая, что ${\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

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

1. О так называемом алгоритме SPFA
2. Мур, Эдвард Ф. (1959). «Кратчайший путь через лабиринт». Материалы Международного симпозиума по теории переключения.. Издательство Гарвардского университета. С. 285–292.
3. http://codeforces.com/blog/entry/16221
4. "Самый быстрый алгоритм кратчайшего пути". Wcipeg.
5. Кэ, Ян. «Худший тестовый пример для SPFA».