algorithm
Алгоритм Флойда-Варшалла

Алгоритм всех парных кратчайших путей

Алгоритм Флойда-Варшалла заключается в поиске кратчайших путей в взвешенном графе с положительными или отрицательными весами ребер. Однократное выполнение алгоритма найдет длины (суммированные веса) кратчайших путей между всеми парами вершин. С небольшим изменением он может печатать кратчайший путь и может обнаруживать отрицательные циклы в графике. Floyd-Warshall - это алгоритм динамического программирования.

Давайте посмотрим на пример. Мы будем применять алгоритм Флойда-Варшалла на этом графике:

Первое, что мы делаем, - взять две двумерные матрицы. Это матрицы смежности . Размер матриц будет полным числом вершин. Для нашего графика возьмем 4 * 4 матрицы. Матрица расстояний будет хранить минимальное расстояние, найденное до сих пор между двумя вершинами. Сначала для ребер, если есть ребро между uv и расстояние / вес w , мы будем хранить: distance[u][v] = w . Для всех ребер, которые не существуют, мы собираемся положить бесконечность . Матрица пути предназначена для регенерации минимального расстояния между двумя вершинами. Поэтому, если есть путь между u и v , мы собираемся поместить path[u][v] = u . Это означает, что лучший способ прийти к вершине-v из вершины-u - использовать ребро, соединяющее v с u . Если между двумя вершинами нет пути, мы собираемся указать N, указав, что пути нет. Две таблицы для нашего графика будут выглядеть так:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Поскольку нет петли, диагонали устанавливаются N. И расстояние от самой вершины равно 0 .

Чтобы применить алгоритм Флойда-Варшалла, мы будем выбирать среднюю вершину k . Тогда для каждой вершины i мы проверим, можем ли мы перейти от i к k, а затем к к j , где j - другая вершина и минимизирующая стоимость перехода от i к j . Если текущее расстояние [i] [j] больше расстояния [i] [k] + расстояние [k] [j] , мы собираемся положить расстояние [i] [j] равным суммированию этих двух расстояний , И путь [i] [j] будет установлен в путь [k] [j] , так как лучше перейти от i к k , а затем к к j . Все вершины будут выбраны как k . У нас будет 3 вложенных цикла: для k, идущих от 1 до 4, я иду от 1 до 4 и j идет от 1 до 4. Мы собираемся проверить:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Итак, что мы в основном проверяем, для каждой пары вершин мы получаем более короткое расстояние, пройдя через другую вершину? Общее количество операций для нашего графика будет 4 * 4 * 4 = 64 . Это означает, что мы будем делать эту проверку 64 раза. Давайте посмотрим на некоторые из них:

Когда k = 1 , i = 2 и j = 3 , расстояние [i] [j] равно -2 , что не больше расстояния [i] [k] + расстояние [k] [j] = -2 + 0 = -2 . Таким образом, он останется неизменным. Опять же, когда k = 1 , i = 4 и j = 2 , расстояние [i] [j] = бесконечность , что больше расстояния [i] [k] + расстояние [k] [j] = 1 + 3 = 4 , Таким образом, мы положили расстояние [i] [j] = 4 и положили путь [i] [j] = path [k] [j] = 1 . Это означает, что для перехода от вершины-4 к вершине-2 путь 4-> 1-> 2 короче существующего пути. Так мы заполняем обе матрицы. Расчет для каждого шага показан здесь . После внесения необходимых изменений наши матрицы будут выглядеть так:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Это наша кратчайшая матрица расстояния. Например, кратчайшее расстояние от 1 до 4 равно 3, а кратчайшее расстояние между 4 и 3 равно 2 . Наш псевдокод будет:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Печать пути:

Чтобы напечатать путь, мы проверим матрицу Path . Чтобы напечатать путь от u до v , мы начнем с пути [u] [v] . Мы установим изменение v = path [u] [v], пока не найдем путь [u] [v] = u и не выталкиваем все значения пути [u] [v] в стеке. После нахождения u , мы напечатаем u и начнем выскакивать элементы из стека и печатать их. Это работает, потому что в матрице пути хранится значение вершины, которое имеет самый короткий путь к v из любого другого узла. Псевдокод будет:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Поиск отрицательного краевого цикла:

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

Сложность:

Сложность алгоритма Флойда-Варшалла равна O (V³), а сложность пространства: O (V²) .