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²) .