弗洛伊德（Floyd）算法

1.算法原理

算法使用距离矩阵和路由矩阵。

距离矩阵是一个$n\times n$矩阵，以图$G$的$n$个节点为行和列。记为$W=[w_{ij}{]}_{n\times n}$，$w_{ij}$表示图$G$中$v_i$和$v_j$两点之间的路径长度。

路由矩阵是一个$n\times n$矩阵，以图$G$的$n$个节点为行和列。记为$R=[r_{ij}{]}_{n\times n}$ ，其中$r_{ij}$表示$v_i$至$v_j$经过的转接点（中间节点）。

算法的思路是首先写出初始的$W$阵和$R$阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大径长，若后求得的径长比前次径长大或相等则不变。以此不断更新和，直至$W$中的数值收敛。

2.实现流程

1. 写出图$G$初始距离矩阵$W^0=[w_{ij}^0{]}_{n\times n}$，其中

$$w_{ij}^0=\{\begin{array}{ll}{d}_{ij}& 当v_i与v_j间有边,d_{ij}为边(i,j)的长\\ \infty & 当v_i与v_j间没有边\\ 0& i=j\end{array}$$

2. 写出图$G$初始路由矩阵$R^0=[r_{ij}^0{]}_{n\times n}$，其中

$$r_{ij}^0=\{\begin{array}{ll}j& 当w_{ij}^0<\infty \\ 0& 当w_{ij}^0=\infty 或i=j时\end{array}$$

3. 循环变量$k$初始值为1
4. 以$k$为中间节点时，求第$k$次修改距离矩阵$W^k=[w_{ij}^k{]}_{n\times n}$，其中

wijk=min⁡{wijk−1,wikk−1+wkjk−1} w^k_{ij}=\min\{w^{k-1}_{ij},w^{k-1}_{ik}+w^{k-1}_{kj}\} wijk​=min{wijk−1​,wikk−1​+wkjk−1​}

5. 以$k$为中间节点时，求第$k$次修改路由矩阵$R^k=[r_{ij}^k{]}_{n\times n}$，其中

$$r_{ij}^k=\{\begin{array}{ll}k& w_{ij}^{k-1}>w_{ik}^{k-1}+w_{kj}^{k-1},即w_{ij}改动时\\ r_{ij}^{k-1}& w_{ij}^{k-1}<w_{ik}^{k-1}+w_{kj}^{k-1},即w_{ij}没有改动时\end{array}$$

6. 循环直至$k=n$结束

3.举个例子

如图：

1. 首先根据图得出初始化距离矩阵：

$$W^0=\left(\begin{array}{ccccccc}0& \infty & \infty & 1.2& 9.2& \infty & 0.5\\ \infty & 0& \infty & 5& \infty & 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& \infty & \infty \\ 9.2& \infty & \infty & 6.7& 0& 15.6& \infty \\ \infty & 3.1& 4& \infty & 15.6& 0& \infty \\ 0.5& 2& 1.5& \infty & \infty & \infty & 0\end{array}\right)$$

并由此得出初始路由矩阵：
$$R^0=\left(\begin{array}{ccccccc}0& 0& 0& 4& 5& 0& 7\\ 0& 0& 0& 4& 0& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& 0& 0\\ 1& 0& 0& 4& 0& 6& 0\\ 0& 2& 3& 0& 5& 0& 0\\ 1& 2& 3& 0& 0& 0& 0\end{array}\right)$$
路由矩阵表示，初始时，$v_1$可以直接到达$v_4$、$v_5$、$v_7$；$v_2$可以直接到达$v_4$，$v_6$，$v_7$；$v_3$可以直接到达$v_6$，$v_7$；…………

2. 然后，把$v_1$作为转节点，因为$v_1$能到达$v_4$、$v_5$、$v_7$，那么$v_2$到$v_7$的这6个点中，能够到达$v_1$的点就能够通过$v_1$再到达$v_4$、$v_5$、$v_7$，由此我们可以对距离矩阵$W^0$进行更新：
   • $v_4$到$v_1$的距离是1.2，$v_1$再到$v_5$的距离是9.2，所以$v_4$经过$v_1$再到$v_5$的距离是10.4，但$v_4$直接到$v_5$的距离是6.7，比10.4小，所以不用改；而$v_4$经过$v_1$再到$v_7$的距离是1.2+0.5=1.7，比$\infty$小，需要进行修改$w_{47}^1=1.7$
   • $v_5$到$v_1$的距离是9.2，$v_5$经过$v_1$再到$v_7$的距离是9.2+0.5=9.7，比$\infty$小，需要进行修改$w_{57}^1=9.7$
   • 同理$w_{74}^1=1.7$，$w_{75}^1=9.7$

于是得到：
$$W^1=\left(\begin{array}{ccccccc}0& \infty & \infty & 1.2& 9.2& \infty & 0.5\\ \infty & 0& \infty & 5& \infty & 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& \infty & \ast 1.7\\ 9.2& \infty & \infty & 6.7& 0& 15.6& \ast 9.7\\ \infty & 3.1& 4& \infty & 15.6& 0& \infty \\ 0.5& 2& 1.5& \ast 1.7& \ast 9.7& \infty & 0\end{array}\right)(\ast 标注修改的值)$$
对于路由矩阵，$v_4$到$v_7$经过了转节点$v_1$，故$r_{47}^1=1$；$v_5$到$v_7$经过了转节点$v_1$，故$r_{57}^1=1$；同理$r_{74}^1=1$，$r_{75}^1=1$
$$R^1=\left(\begin{array}{ccccccc}0& 0& 0& 4& 5& 0& 7\\ 0& 0& 0& 4& 0& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& 0& \ast 1\\ 1& 0& 0& 4& 0& 6& \ast 1\\ 0& 2& 3& 0& 5& 0& 0\\ 1& 2& 3& \ast 1& \ast 1& 0& 0\end{array}\right)(\ast 标注修改的值)$$

3. 把$v_2$作为转节点，重复上面的步骤，可以得到

距离矩阵：
$$W^2=\left(\begin{array}{ccccccc}0& \infty & \infty & 1.2& 9.2& \infty & 0.5\\ \infty & 0& \infty & 5& \infty & 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& \ast 8.1& 1.7\\ 9.2& \infty & \infty & 6.7& 0& 15.6& 9.7\\ \infty & 3.1& 4& \ast 8.1& 15.6& 0& \ast 5.1\\ 0.5& 2& 1.5& 1.7& 9.7& \ast 5.1& 0\end{array}\right)(\ast 标注修改的值)$$
路由矩阵：
$$R^2=\left(\begin{array}{ccccccc}0& 0& 0& 4& 5& 0& 7\\ 0& 0& 0& 4& 0& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& \ast 2& 1\\ 1& 0& 0& 4& 0& 6& 1\\ 0& 2& 3& \ast 2& 5& 0& \ast 2\\ 1& 2& 3& 1& 1& \ast 2& 0\end{array}\right)(\ast 标注修改的值)$$

4. 把$v_3$作为转节点，发现并没有要修改的值

距离矩阵：
$$W^3=\left(\begin{array}{ccccccc}0& \infty & \infty & 1.2& 9.2& \infty & 0.5\\ \infty & 0& \infty & 5& \infty & 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& 8.1& 1.7\\ 9.2& \infty & \infty & 6.7& 0& 15.6& 9.7\\ \infty & 3.1& 4& 8.1& 15.6& 0& 5.1\\ 0.5& 2& 1.5& 1.7& 9.7& 5.1& 0\end{array}\right)$$
路由矩阵：
$$R^3=\left(\begin{array}{ccccccc}0& 0& 0& 4& 5& 0& 7\\ 0& 0& 0& 4& 0& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& 2& 1\\ 1& 0& 0& 4& 0& 6& 1\\ 0& 2& 3& 2& 5& 0& 2\\ 1& 2& 3& 1& 1& 2& 0\end{array}\right)$$

5. $v_4$作为转接点

距离矩阵：
$$W^4=\left(\begin{array}{ccccccc}0& \ast 6.2& \infty & 1.2& \ast 7.9& \ast 9.3& 0.5\\ \ast 6.2& 0& \infty & 5& \ast 11.7& 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& 8.1& 1.7\\ \ast 7.9& \ast 11.7& \infty & 6.7& 0& \ast 14.8& \ast 8.4\\ \ast 9.3& 3.1& 4& 8.1& \ast 14.8& 0& 5.1\\ 0.5& 2& 1.5& 1.7& \ast 8.4& 5.1& 0\end{array}\right)(\ast 标注修改的值)$$
路由矩阵：
$$R^4=\left(\begin{array}{ccccccc}0& 4& 0& 4& 4& 4& 7\\ 4& 0& 0& 4& 4& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& 2& 1\\ 4& 4& 0& 4& 0& 4& 4\\ 4& 2& 3& 2& 4& 0& 2\\ 1& 2& 3& 1& 4& 2& 0\end{array}\right)$$

6. $v_5$作为转接点，无需修改

距离矩阵：
$$W^5=\left(\begin{array}{ccccccc}0& 6.2& \infty & 1.2& 7.9& 9.3& 0.5\\ 6.2& 0& \infty & 5& 11.7& 3.1& 2\\ \infty & \infty & 0& \infty & \infty & 4& 1.5\\ 1.2& 5& \infty & 0& 6.7& 8.1& 1.7\\ 7.9& 11.7& \infty & 6.7& 0& 14.8& 8.4\\ 9.3& 3.1& 4& 8.1& 14.8& 0& 5.1\\ 0.5& 2& 1.5& 1.7& 8.4& 5.1& 0\end{array}\right)$$
路由矩阵：
$$R^5=\left(\begin{array}{ccccccc}0& 4& 0& 4& 4& 4& 7\\ 4& 0& 0& 4& 4& 6& 7\\ 0& 0& 0& 0& 0& 6& 7\\ 1& 2& 0& 0& 5& 2& 1\\ 4& 4& 0& 4& 0& 4& 4\\ 4& 2& 3& 2& 4& 0& 2\\ 1& 2& 3& 1& 4& 2& 0\end{array}\right)$$

7. $v_6$作为转接点

距离矩阵：
$$W^6=\left(\begin{array}{ccccccc}0& 6.2& \ast 13.3& 1.2& 7.9& 9.3& 0.5\\ 6.2& 0& \ast 7.1& 5& 11.7& 3.1& 2\\ \ast 13.3& \ast 7.1& 0& \ast 12.1& \ast 18.8& 4& 1.5\\ 1.2& 5& \ast 12.1& 0& 6.7& 8.1& 1.7\\ 7.9& 11.7& \ast 18.8& 6.7& 0& 14.8& 8.4\\ 9.3& 3.1& 4& 8.1& 14.8& 0& 5.1\\ 0.5& 2& 1.5& 1.7& 8.4& 5.1& 0\end{array}\right)$$
路由矩阵：
$$R^6=\left(\begin{array}{ccccccc}0& 4& 6& 4& 4& 4& 7\\ 4& 0& 6& 4& 4& 6& 7\\ 6& 6& 0& 6& 6& 6& 7\\ 1& 2& 6& 0& 5& 2& 1\\ 4& 4& 6& 4& 0& 4& 4\\ 4& 2& 3& 2& 4& 0& 2\\ 1& 2& 3& 1& 4& 2& 0\end{array}\right)$$

8. $v_7$作为转接点

距离矩阵：
$$W^7=\left(\begin{array}{ccccccc}0& \ast 2.5& \ast 2& 1.2& 7.9& \ast 5.6& 0.5\\ \ast 2.5& 0& \ast 3.5& \ast 3.7& \ast 10.4& 3.1& 2\\ \ast 2& \ast 3.5& 0& \ast 3.2& \ast 9.9& 4& 1.5\\ 1.2& \ast 3.7& \ast 3.2& 0& 6.7& \ast 6.8& 1.7\\ 7.9& \ast 10.4& \ast 9.9& 6.7& 0& \ast 13.5& 8.4\\ \ast 5.6& 3.1& 4& \ast 6.8& \ast 13.5& 0& 5.1\\ 0.5& 2& 1.5& 1.7& 8.4& 5.1& 0\end{array}\right)$$
路由矩阵：
$$R^7=\left(\begin{array}{ccccccc}0& 7& 7& 4& 4& 7& 7\\ 7& 0& 7& 7& 7& 6& 7\\ 7& 7& 0& 7& 7& 6& 7\\ 1& 7& 7& 0& 5& 7& 1\\ 4& 7& 7& 4& 0& 7& 4\\ 7& 2& 3& 7& 7& 0& 2\\ 1& 2& 3& 1& 4& 2& 0\end{array}\right)$$
从$W^7$和$R^7$可以找到任何两个节点间最短径的径长和路由。

4.实现代码

matrix = [[0, -1, -1, 1.2, 9.1, -1, 0.5],
          [-1, 0, -1, 5, -1, 3.1, 2],
          [-1, -1, 0, -1, -1, 4, 1.5],
          [1.2, 5, -1, 0, 6.7, -1, -1],
          [9.2, -1, -1, 6.7, 0, 15.6, -1],
          [-1, 3.1, 4, -1, 15.6, 0, -1],
          [0.5, 2, 1.5, -1, -1, -1, 0]]


def floyd(W):
    # 首先获取节点数
    node_number = len(W)

    # 初始化路由矩阵
    R = [[0 for i in range(node_number)] for j in range(node_number)]
    for i in range(node_number):
        for j in range(node_number):
            if W[i][j] > 0:
                R[i][j] = j+1
            else:
                R[i][j] = 0
    # 查看初始化的路由矩阵
    for row in R:
        print(row)

    # 循环求W_n和R_n
    for k in range(node_number):
        for i in range(node_number):
            for j in range(node_number):
                if W[i][k] > 0 and W[k][j] > 0 and (W[i][k] + W[k][j] < W[i][j] or W[i][j] == -1):
                    W[i][j] = W[i][k] + W[k][j]
                    R[i][j] = k+1
        print("第%d次循环:" % (k+1))
        print("距离矩阵:")
        for row in W:
            print(row)
        print("路由矩阵:")
        for row in R:
            print(row)


floyd(matrix)

5.输出结果

"""
[0, 0, 0, 4, 5, 0, 7]
[0, 0, 0, 4, 0, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 0, 0]
[1, 0, 0, 4, 0, 6, 0]
[0, 2, 3, 0, 5, 0, 0]
[1, 2, 3, 0, 0, 0, 0]
第1次循环:
距离矩阵:
[0, -1, -1, 1.2, 9.1, -1, 0.5]
[-1, 0, -1, 5, -1, 3.1, 2]
[-1, -1, 0, -1, -1, 4, 1.5]
[1.2, 5, -1, 0, 6.7, -1, 1.7]
[9.2, -1, -1, 6.7, 0, 15.6, 9.7]
[-1, 3.1, 4, -1, 15.6, 0, -1]
[0.5, 2, 1.5, 1.7, 9.6, -1, 0]
路由矩阵:
[0, 0, 0, 4, 5, 0, 7]
[0, 0, 0, 4, 0, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 0, 1]
[1, 0, 0, 4, 0, 6, 1]
[0, 2, 3, 0, 5, 0, 0]
[1, 2, 3, 1, 1, 0, 0]
第2次循环:
距离矩阵:
[0, -1, -1, 1.2, 9.1, -1, 0.5]
[-1, 0, -1, 5, -1, 3.1, 2]
[-1, -1, 0, -1, -1, 4, 1.5]
[1.2, 5, -1, 0, 6.7, 8.1, 1.7]
[9.2, -1, -1, 6.7, 0, 15.6, 9.7]
[-1, 3.1, 4, 8.1, 15.6, 0, 5.1]
[0.5, 2, 1.5, 1.7, 9.6, 5.1, 0]
路由矩阵:
[0, 0, 0, 4, 5, 0, 7]
[0, 0, 0, 4, 0, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 2, 1]
[1, 0, 0, 4, 0, 6, 1]
[0, 2, 3, 2, 5, 0, 2]
[1, 2, 3, 1, 1, 2, 0]
第3次循环:
距离矩阵:
[0, -1, -1, 1.2, 9.1, -1, 0.5]
[-1, 0, -1, 5, -1, 3.1, 2]
[-1, -1, 0, -1, -1, 4, 1.5]
[1.2, 5, -1, 0, 6.7, 8.1, 1.7]
[9.2, -1, -1, 6.7, 0, 15.6, 9.7]
[-1, 3.1, 4, 8.1, 15.6, 0, 5.1]
[0.5, 2, 1.5, 1.7, 9.6, 5.1, 0]
路由矩阵:
[0, 0, 0, 4, 5, 0, 7]
[0, 0, 0, 4, 0, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 2, 1]
[1, 0, 0, 4, 0, 6, 1]
[0, 2, 3, 2, 5, 0, 2]
[1, 2, 3, 1, 1, 2, 0]
第4次循环:
距离矩阵:
[0, 6.2, -1, 1.2, 7.9, 9.299999999999999, 0.5]
[6.2, 0, -1, 5, 11.7, 3.1, 2]
[-1, -1, 0, -1, -1, 4, 1.5]
[1.2, 5, -1, 0, 6.7, 8.1, 1.7]
[7.9, 11.7, -1, 6.7, 0, 14.8, 8.4]
[9.299999999999999, 3.1, 4, 8.1, 14.8, 0, 5.1]
[0.5, 2, 1.5, 1.7, 8.4, 5.1, 0]
路由矩阵:
[0, 4, 0, 4, 4, 4, 7]
[4, 0, 0, 4, 4, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 2, 1]
[4, 4, 0, 4, 0, 4, 4]
[4, 2, 3, 2, 4, 0, 2]
[1, 2, 3, 1, 4, 2, 0]
第5次循环:
距离矩阵:
[0, 6.2, -1, 1.2, 7.9, 9.299999999999999, 0.5]
[6.2, 0, -1, 5, 11.7, 3.1, 2]
[-1, -1, 0, -1, -1, 4, 1.5]
[1.2, 5, -1, 0, 6.7, 8.1, 1.7]
[7.9, 11.7, -1, 6.7, 0, 14.8, 8.4]
[9.299999999999999, 3.1, 4, 8.1, 14.8, 0, 5.1]
[0.5, 2, 1.5, 1.7, 8.4, 5.1, 0]
路由矩阵:
[0, 4, 0, 4, 4, 4, 7]
[4, 0, 0, 4, 4, 6, 7]
[0, 0, 0, 0, 0, 6, 7]
[1, 2, 0, 0, 5, 2, 1]
[4, 4, 0, 4, 0, 4, 4]
[4, 2, 3, 2, 4, 0, 2]
[1, 2, 3, 1, 4, 2, 0]
第6次循环:
距离矩阵:
[0, 6.2, 13.299999999999999, 1.2, 7.9, 9.299999999999999, 0.5]
[6.2, 0, 7.1, 5, 11.7, 3.1, 2]
[13.299999999999999, 7.1, 0, 12.1, 18.8, 4, 1.5]
[1.2, 5, 12.1, 0, 6.7, 8.1, 1.7]
[7.9, 11.7, 18.8, 6.7, 0, 14.8, 8.4]
[9.299999999999999, 3.1, 4, 8.1, 14.8, 0, 5.1]
[0.5, 2, 1.5, 1.7, 8.4, 5.1, 0]
路由矩阵:
[0, 4, 6, 4, 4, 4, 7]
[4, 0, 6, 4, 4, 6, 7]
[6, 6, 0, 6, 6, 6, 7]
[1, 2, 6, 0, 5, 2, 1]
[4, 4, 6, 4, 0, 4, 4]
[4, 2, 3, 2, 4, 0, 2]
[1, 2, 3, 1, 4, 2, 0]
第7次循环:
距离矩阵:
[0, 2.5, 2.0, 1.2, 7.9, 5.6, 0.5]
[2.5, 0, 3.5, 3.7, 10.4, 3.1, 2]
[2.0, 3.5, 0, 3.2, 9.9, 4, 1.5]
[1.2, 3.7, 3.2, 0, 6.7, 6.8, 1.7]
[7.9, 10.4, 9.9, 6.7, 0, 13.5, 8.4]
[5.6, 3.1, 4, 6.8, 13.5, 0, 5.1]
[0.5, 2, 1.5, 1.7, 8.4, 5.1, 0]
路由矩阵:
[0, 7, 7, 4, 4, 7, 7]
[7, 0, 7, 7, 7, 6, 7]
[7, 7, 0, 7, 7, 6, 7]
[1, 7, 7, 0, 5, 7, 1]
[4, 7, 7, 4, 0, 7, 4]
[7, 2, 3, 7, 7, 0, 2]
[1, 2, 3, 1, 4, 2, 0]
"""