Floyd-Warshall 算法
Floyd-Warshall 算法是一种图算法，用于查找加权图中所有顶点之间的最短路径。该算法与其他最短路径算法不同；简单来说，该算法使用图中的每个顶点作为枢轴，检查它是否提供了从一个点到另一个点的最短路径。
Floyd-Warshall 算法适用于有向和无向加权图，除非这些图中不包含任何负循环。负环是指图中所有边的和不能为负数。
由于该算法处理的是重叠子问题——作为枢轴的顶点找到的路径会被存储起来以便后续步骤求解——因此它使用动态规划方法。
Floyd-Warshall 算法是全对最短路径算法中的一种方法，它使用图的邻接矩阵表示来求解。
Floyd-Warshall 算法
考虑一个图，G = {V, E}，其中 V 是图中所有顶点的集合，E 是图中所有边的集合。图 G 以邻接矩阵 A 的形式表示，该矩阵包含连接两个顶点的每条边的所有权重。
算法
步骤 1 − 构造一个邻接矩阵 A，其中包含图中所有边的代价。如果两个顶点之间没有路径，则将该值标记为 ∞。
步骤 2 − 从 A 导出另一个邻接矩阵 A1，并保持原始邻接矩阵的第一行和第一列不变，使其保留在 A1 中。对于剩余的值，例如 A1[i,j]，如果 A[i,j]>A[i,k]+A[k,j]，则将 A1[i,j] 替换为 A[i,k]+A[k,j]。否则，请勿更改这些值。在此步骤中，k = 1（第一个顶点作为枢轴）。
步骤 3 − 对图中的所有顶点重复 步骤 2，更改每个枢轴顶点的 k 值，直到获得最终矩阵。
步骤 4 −最终得到的邻接矩阵即为包含所有最短路径的最终解。
伪代码
Floyd-Warshall(w, n){ // w: weights, n: number of vertices
for i = 1 to n do // initialize, D (0) = [wij]
for j = 1 to n do{
d[i, j] = w[i, j];
}
for k = 1 to n do // Compute D (k) from D (k-1)
for i = 1 to n do
for j = 1 to n do
if (d[i, k] + d[k, j] < d[i, j]){
d[i, j] = d[i, k] + d[k, j];
}
return d[1..n, 1..n];
}
示例
考虑以下有向加权图 G = {V, E}。使用 Floyd-Warshall 算法查找图中所有顶点之间的最短路径。
解决方案
步骤 1
构建一个邻接矩阵 A，其中包含所有距离值。
$$A=\begin{matrix} 0 & 5& \infty & 6& \infty \ \infty & 0& 1& \infty& 7\ 3 & \infty& 0& 4& \infty\ \infty & \infty& 2& 0& 3\ 2& \infty& \infty& 5& 0\ \end{matrix}$$
步骤 2
将上述邻接矩阵作为输入，仅保留第一行和第一列，导出另一个矩阵 A0。取 k = 1，并将所有其他值替换为 A[i,k]+A[k,j]。
$$A=\begin{matrix} 0 & 5& \infty & 6& \infty \ \infty & & & & \ 3& & & & \ \infty& & & & \ 2& & & & \ \end{matrix}$$
$$A_{1}=\begin{matrix} 0 & 5& \infty & 6& \infty \ \infty & 0& 1& \infty& 7\ 3 & 8& 0& 4& \infty\ \infty & \infty& 2& 0& 3\ 2& 7& \infty& 5& 0\ \end{matrix}$$
步骤 3
将上述邻接矩阵作为输入，通过仅保留第一行和第一列来导出另一个矩阵 A0。取 k = 1，并将所有其他值替换为 A[i,k]+A[k,j]。
$$A_{2}=\begin{matrix} & 5& & & \ \infty & 0& 1& \infty& 7\ & 8& & & \ & \infty& & & \ & 7& & & \ \end{matrix}$$
$$A_{2}=\begin{matrix} 0 & 5& 6& 6& 12 \ \infty & 0& 1& \infty& 7\ 3 & 8& 0& 4& 15\ \infty & \infty& 2& 0& 3\ 2 & 7& 8& 5& 0 \ \end{matrix}$$
步骤 4
将上述邻接矩阵作为输入，通过仅保留第一行和第一列，导出另一个矩阵 A0。取 k = 1，并将所有其他值替换为 A[i,k]+A[k,j]。
$$A_{3}=\begin{matrix} & & 6& & \ & & 1& & \ 3 & 8& 0& 4& 15\ & & 2& & \ & & 8& & \ \end{matrix}$$
$$A_{3}=\begin{matrix} 0 & 5& 6& 6& 12 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 15\ 5 & 10& 2& 0& 3\ 2 & 7& 8& 5& 0 \ \end{matrix}$$
步骤 5
将上述邻接矩阵作为输入，通过仅保留第一行和第一列，导出另一个矩阵 A0。取 k = 1，并将所有其他值替换为 A[i,k]+A[k,j]。
$$A_{4}=\begin{matrix} & & & 6& \ & & & 5& \ & & & 4& \ 5 & 10& 2& 0& 3\ & & & 5& \ \end{matrix}$$
$$A_{4}=\begin{matrix} 0 & 5& 6& 6& 9 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 7\ 5 & 10& 2& 0& 3\ 2 & 7& 7& 5& 0 \ \end{matrix}$$
步骤 6
将上述邻接矩阵作为输入，通过仅保留第一行和第一列，导出另一个矩阵 A0。取 k = 1，并将所有其他值替换为 A[i,k]+A[k,j]。
$$A_{5}=\begin{matrix} & & & & 9 \ & & & & 7\ & & & & 7\ & & & & 3\ 2 & 7& 7& 5& 0 \ \end{matrix}$$
$$A_{5}=\begin{matrix} 0 & 5& 6& 6& 9 \ 4 & 0& 1& 5& 7\ 3 & 8& 0& 4& 7\ 5 & 10& 2& 0& 3\ 2 & 7& 7& 5& 0 \ \end{matrix}$$
分析
从上面的伪代码可以看出，Floyd-Warshall 算法使用三个 for 循环来查找图中所有顶点对之间的最短距离。因此，Floyd-Warshall 算法的时间复杂度为 O(n3)，其中 n 是图中的顶点数。该算法的空间复杂度为 O(n2)。
实现
以下是 Floyd Warshall 算法的实现，该算法使用成本邻接矩阵查找图中的最短路径 -
#include <stdio.h>
void floyds(int b[3][3]) {
int i, j, k;
for (k = 0; k < 3; k++) {
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if ((b[i][k] * b[k][j] != 0) && (i != j)) {
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 3; i++) {
printf("相对于节点的最低成本： %d
", i);
for (j = 0; j < 3; j++) {
printf("%d ", b[i][j]);
}
}
}
int main() {
int b[3][3] = {0};
b[0][1] = 10;
b[1][2] = 15;
b[2][0] = 12;
floyds(b);
return 0;
}
输出
相对于节点的最低成本： 0 0 10 25 相对于节点的最低成本： 1 27 0 15 相对于节点的最低成本： 2 12 22 0
#include <iostream>
using namespace std;
void floyds(int b[][3]){
int i, j, k;
for (k = 0; k < 3; k++) {
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if ((b[i][k] * b[k][j] != 0) && (i != j)) {
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 3; i++) {
cout<<"相对于节点的最低成本："<<i<<endl;
for (j = 0; j < 3; j++) {
cout<<b[i][j]<<" ";
}
}
}
int main(){
int b[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = 0;
}
}
b[0][1] = 10;
b[1][2] = 15;
b[2][0] = 12;
floyds(b);
return 0;
}
输出
相对于节点的最低成本：0 0 10 25 相对于节点的最低成本：1 27 0 15 相对于节点的最低成本：2 12 22 0
import java.util.Arrays;
public class Main {
public static void floyds(int[][] b) {
int i, j, k;
for (k = 0; k < 3; k++) {
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if ((b[i][k] * b[k][j] != 0) && (i != j)) {
if ((b[i][k] + b[k][j] < b[i][j]) || (b[i][j] == 0)) {
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
}
for (i = 0; i < 3; i++) {
System.out.println("相对于节点的最低成本：" + i);
for (j = 0; j < 3; j++) {
System.out.print(b[i][j] + " ");
}
}
}
public static void main(String[] args) {
int[][] b = new int[3][3];
for (int i = 0; i < 3; i++) {
Arrays.fill(b[i], 0);
}
b[0][1] = 10;
b[1][2] = 15;
b[2][0] = 12;
floyds(b);
}
}
输出
相对于节点的最低成本：0 0 10 25 相对于节点的最低成本：1 27 0 15 相对于节点的最低成本：2 12 22 0
import numpy as np
def floyds(b):
for k in range(3):
for i in range(3):
for j in range(3):
if (b[i][k] * b[k][j] != 0) and (i != j):
if (b[i][k] + b[k][j] < b[i][j]) or (b[i][j] == 0):
b[i][j] = b[i][k] + b[k][j]
for i in range(3):
print("相对于节点的最低成本：", i)
for j in range(3):
print(b[i][j], end=" ")
b = np.zeros((3, 3), dtype=int)
b[0][1] = 10
b[1][2] = 15
b[2][0] = 12
#calling the method
floyds(b)
输出
相对于节点的最低成本： 0 0 10 25 相对于节点的最低成本： 1 27 0 15 相对于节点的最低成本： 2 12 22 0
