弗洛伊德（Floyd）算法 python实现
弗洛伊德（Floyd）算法1.算法原理算法使用距离矩阵和路由矩阵。距离矩阵是一个n×nn \times nn×n矩阵，以图GGG的nnn个节点为行和列。记为W=[wij]n×nW=[w_{ij}]_{n\times n}W=[wij]n×n，wijw_{ij}wij表示图GGG中viv_ivi和vjv_jvj两点之间的路径长度。接点则记录最后一个）。路由矩阵是一个n×nn\times n
弗洛伊德（Floyd）算法
1.算法原理
算法使用距离矩阵和路由矩阵。
距离矩阵是一个 n × n n \times n n×n矩阵，以图 G G G的 n n n个节点为行和列。记为 W = [ w i j ] n × n W=[w_{ij}]_{n\times n} W=[wij]n×n， w i j w_{ij} wij表示图 G G G中 v i v_i vi和 v j v_j vj两点之间的路径长度。
路由矩阵是一个 n × n n\times n n×n矩阵，以图 G G G的 n n n个节点为行和列。记为 R = [ r i j ] n × n R =[r_{ij}]_{n\times n} R=[rij]n×n ，其中 r i j r_{ij} rij表示 v i v_i vi至 v j v_j vj经过的转接点（中间节点）。
算法的思路是首先写出初始的 W W W阵和 R R R阵，接着按顺序依次将节点集中的各个节点作为中间节点，计算此点距其他各点的径长，每次计算后都以求得的与上次相比较小的径长去更新前一次较大径长，若后求得的径长比前次径长大或相等则不变。以此不断更新和，直至 W W W中的数值收敛。
2.实现流程
- 写出图 G G G初始距离矩阵 W 0 = [ w i j 0 ] n × n W^0=[w^0_{ij}]_{n\times n} W0=[wij0]n×n，其中
w i j 0 = { d i j 当 v i 与 v j 间有边 , d i j 为边 ( i , j ) 的长 ∞ 当 v i 与 v j 间没有边 0 i = j w^0_{ij}= \begin{cases} d_{ij} & {当v_i与v_j间有边,d_{ij}为边(i,j)的长} \\ \infin & {当v_i与v_j间没有边}\\ 0 & {i=j}\\ \end{cases} wij0=⎩ ⎨ ⎧dij∞0当vi与vj间有边,dij为边(i,j)的长当vi与vj间没有边i=j
- 写出图 G G G初始路由矩阵 R 0 = [ r i j 0 ] n × n R^0=[r^0_{ij}]_{n\times n} R0=[rij0]n×n，其中
r i j 0 = { j 当 w i j 0 < ∞ 0 当 w i j 0 = ∞ 或 i = j 时 r^0_{ij}= \begin{cases} j & {当w^0_{ij}<\infin} \\ 0 & {当w^0_{ij}=\infin或i=j时}\\ \end{cases} rij0={j0当wij0<∞当wij0=∞或i=j时
- 循环变量 k k k初始值为1
- 以 k k k为中间节点时，求第 k k k次修改距离矩阵 W k = [ w i j k ] n × n W^k=[w^k_{ij}]_{n\times n} Wk=[wijk]n×n，其中
w i j k = min { w i j k − 1 , w i k k − 1 + w k j k − 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}
- 以 k k k为中间节点时，求第 k k k次修改路由矩阵 R k = [ r i j k ] n × n R^k=[r^k_{ij}]_{n\times n} Rk=[rijk]n×n，其中
r i j k = { k w i j k − 1 > w i k k − 1 + w k j k − 1 , 即 w i j 改动时 r i j k − 1 w i j k − 1 < w i k k − 1 + w k j k − 1 , 即 w i j 没有改动时 r^k_{ij}= \begin{cases} k & {w^{k-1}_{ij}>w^{k-1}_{ik}+w^{k-1}_{kj},即w_{ij}改动时} \\ r^{k-1}_{ij} & {w^{k-1}_{ij}<w^{k-1}_{ik}+w^{k-1}_{kj},即w_{ij}没有改动时}\\ \end{cases} rijk={krijk−1wijk−1>wikk−1+wkjk−1,即wij改动时wijk−1<wikk−1+wkjk−1,即wij没有改动时
- 循环直至 k = n k=n k=n结束
3.举个例子
如图：
- 首先根据图得出初始化距离矩阵：
W 0 = ( 0 ∞ ∞ 1.2 9.2 ∞ 0.5 ∞ 0 ∞ 5 ∞ 3.1 2 ∞ ∞ 0 ∞ ∞ 4 1.5 1.2 5 ∞ 0 6.7 ∞ ∞ 9.2 ∞ ∞ 6.7 0 15.6 ∞ ∞ 3.1 4 ∞ 15.6 0 ∞ 0.5 2 1.5 ∞ ∞ ∞ 0 ) W^0= \begin{pmatrix} 0 & \infin & \infin & 1.2 & 9.2 & \infin & 0.5 \\ \infin & 0 & \infin & 5 & \infin & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & \infin & \infin \\ 9.2 & \infin & \infin & 6.7 & 0 & 15.6 & \infin \\ \infin & 3.1 & 4 & \infin & 15.6 & 0 & \infin \\ 0.5 & 2 & 1.5 & \infin & \infin & \infin & 0 \end{pmatrix} W0= 0∞∞1.29.2∞0.5∞0∞5∞3.12∞∞0∞∞41.51.25∞06.7∞∞9.2∞∞6.7015.6∞∞3.14∞15.60∞0.521.5∞∞∞0
并由此得出初始路由矩阵：
R
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
0
1
0
0
4
0
6
0
0
2
3
0
5
0
0
1
2
3
0
0
0
0
)
R^0= \begin{pmatrix} 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{pmatrix}
R0=
0001101000202200000334400400500505006606007770000
路由矩阵表示，初始时，
v
1
v_1
v1可以直接到达
v
4
v_4
v4、
v
5
v_5
v5、
v
7
v_7
v7；
v
2
v_2
v2可以直接到达
v
4
v_4
v4，
v
6
v_6
v6，
v
7
v_7
v7；
v
3
v_3
v3可以直接到达
v
6
v_6
v6，
v
7
v_7
v7；…………
- 然后，把
v
1
v_1
v1作为转节点，因为
v
1
v_1
v1能到达
v
4
v_4
v4、
v
5
v_5
v5、
v
7
v_7
v7，那么
v
2
v_2
v2到
v
7
v_7
v7的这6个点中，能够到达
v
1
v_1
v1的点就能够通过
v
1
v_1
v1再到达
v
4
v_4
v4、
v
5
v_5
v5、
v
7
v_7
v7，由此我们可以对距离矩阵
W
0
W^0
W0进行更新：
- v 4 v_4 v4到 v 1 v_1 v1的距离是1.2， v 1 v_1 v1再到 v 5 v_5 v5的距离是9.2，所以 v 4 v_4 v4经过 v 1 v_1 v1再到 v 5 v_5 v5的距离是10.4，但 v 4 v_4 v4直接到 v 5 v_5 v5的距离是6.7，比10.4小，所以不用改；而 v 4 v_4 v4经过 v 1 v_1 v1再到 v 7 v_7 v7的距离是1.2+0.5=1.7，比 ∞ \infin ∞小，需要进行修改 w 47 1 = 1.7 w^1_{47}=1.7 w471=1.7
- v 5 v_5 v5到 v 1 v_1 v1的距离是9.2， v 5 v_5 v5经过 v 1 v_1 v1再到 v 7 v_7 v7的距离是9.2+0.5=9.7，比 ∞ \infin ∞小，需要进行修改 w 57 1 = 9.7 w^1_{57}=9.7 w571=9.7
- 同理 w 74 1 = 1.7 w^1_{74}=1.7 w741=1.7， w 75 1 = 9.7 w^1_{75}=9.7 w751=9.7
于是得到：
W
1
=
(
0
∞
∞
1.2
9.2
∞
0.5
∞
0
∞
5
∞
3.1
2
∞
∞
0
∞
∞
4
1.5
1.2
5
∞
0
6.7
∞
∗
1.7
9.2
∞
∞
6.7
0
15.6
∗
9.7
∞
3.1
4
∞
15.6
0
∞
0.5
2
1.5
∗
1.7
∗
9.7
∞
0
)
(
∗
标注修改的值
)
W^1= \begin{pmatrix} 0 & \infin & \infin & 1.2 & 9.2 & \infin & 0.5 \\ \infin & 0 & \infin & 5 & \infin & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & \infin & *1.7 \\ 9.2 & \infin & \infin & 6.7 & 0 & 15.6 & *9.7 \\ \infin & 3.1 & 4 & \infin & 15.6 & 0 & \infin \\ 0.5 & 2 & 1.5 & *1.7 & *9.7 & \infin & 0 \end{pmatrix} (*标注修改的值)
W1=
0∞∞1.29.2∞0.5∞0∞5∞3.12∞∞0∞∞41.51.25∞06.7∞∗1.79.2∞∞6.7015.6∗9.7∞3.14∞15.60∞0.521.5∗1.7∗9.7∞0
(∗标注修改的值)
对于路由矩阵，
v
4
v_4
v4到
v
7
v_7
v7经过了转节点
v
1
v_1
v1，故
r
47
1
=
1
r^1_{47}=1
r471=1；
v
5
v_5
v5到
v
7
v_7
v7经过了转节点
v
1
v_1
v1，故
r
57
1
=
1
r^1_{57}=1
r571=1；同理
r
74
1
=
1
r^1_{74}=1
r741=1，
r
75
1
=
1
r^1_{75}=1
r751=1
R
1
=
(
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
)
(
∗
标注修改的值
)
R^1= \begin{pmatrix} 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 \\ \end{pmatrix} (*标注修改的值)
R1=
000110100020220000033440040∗1500505∗10660600777∗1∗100
(∗标注修改的值)
- 把 v 2 v_2 v2作为转节点，重复上面的步骤，可以得到
距离矩阵：
W
2
=
(
0
∞
∞
1.2
9.2
∞
0.5
∞
0
∞
5
∞
3.1
2
∞
∞
0
∞
∞
4
1.5
1.2
5
∞
0
6.7
∗
8.1
1.7
9.2
∞
∞
6.7
0
15.6
9.7
∞
3.1
4
∗
8.1
15.6
0
∗
5.1
0.5
2
1.5
1.7
9.7
∗
5.1
0
)
(
∗
标注修改的值
)
W^2= \begin{pmatrix} 0 & \infin & \infin & 1.2 & 9.2 & \infin & 0.5 \\ \infin & 0 & \infin & 5 & \infin & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & *8.1 & 1.7 \\ 9.2 & \infin & \infin & 6.7 & 0 & 15.6 & 9.7 \\ \infin & 3.1 & 4 & *8.1 & 15.6 & 0 & *5.1 \\ 0.5 & 2 & 1.5 & 1.7 & 9.7 & *5.1 & 0 \end{pmatrix} (*标注修改的值)
W2=
0∞∞1.29.2∞0.5∞0∞5∞3.12∞∞0∞∞41.51.25∞06.7∗8.11.79.2∞∞6.7015.69.7∞3.14∗8.115.60∗5.10.521.51.79.7∗5.10
(∗标注修改的值)
路由矩阵：
R
2
=
(
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
)
(
∗
标注修改的值
)
R^2= \begin{pmatrix} 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{pmatrix} (*标注修改的值)
R2=
00011010002022000003344004∗215005051066∗260∗277711∗20
(∗标注修改的值)
- 把 v 3 v_3 v3作为转节点，发现并没有要修改的值
距离矩阵：
W
3
=
(
0
∞
∞
1.2
9.2
∞
0.5
∞
0
∞
5
∞
3.1
2
∞
∞
0
∞
∞
4
1.5
1.2
5
∞
0
6.7
8.1
1.7
9.2
∞
∞
6.7
0
15.6
9.7
∞
3.1
4
8.1
15.6
0
5.1
0.5
2
1.5
1.7
9.7
5.1
0
)
W^3= \begin{pmatrix} 0 & \infin & \infin & 1.2 & 9.2 & \infin & 0.5 \\ \infin & 0 & \infin & 5 & \infin & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & 8.1 & 1.7 \\ 9.2 & \infin & \infin & 6.7 & 0 & 15.6 & 9.7 \\ \infin & 3.1 & 4 & 8.1 & 15.6 & 0 & 5.1 \\ 0.5 & 2 & 1.5 & 1.7 & 9.7 & 5.1 & 0 \end{pmatrix}
W3=
0∞∞1.29.2∞0.5∞0∞5∞3.12∞∞0∞∞41.51.25∞06.78.11.79.2∞∞6.7015.69.7∞3.148.115.605.10.521.51.79.75.10
路由矩阵：
R
3
=
(
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
)
R^3= \begin{pmatrix} 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{pmatrix}
R3=
0001101000202200000334400421500505106626027771120
- v 4 v_4 v4作为转接点
距离矩阵：
W
4
=
(
0
∗
6.2
∞
1.2
∗
7.9
∗
9.3
0.5
∗
6.2
0
∞
5
∗
11.7
3.1
2
∞
∞
0
∞
∞
4
1.5
1.2
5
∞
0
6.7
8.1
1.7
∗
7.9
∗
11.7
∞
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
)
(
∗
标注修改的值
)
W^4= \begin{pmatrix} 0 & *6.2 & \infin & 1.2 & *7.9 & *9.3 & 0.5 \\ *6.2 & 0 & \infin & 5 & *11.7 & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & 8.1 & 1.7 \\ *7.9 & *11.7 & \infin & 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{pmatrix} (*标注修改的值)
W4=
0∗6.2∞1.2∗7.9∗9.30.5∗6.20∞5∗11.73.12∞∞0∞∞41.51.25∞06.78.11.7∗7.9∗11.7∞6.70∗14.8∗8.4∗9.33.148.1∗14.805.10.521.51.7∗8.45.10
(∗标注修改的值)
路由矩阵：
R
4
=
(
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
)
R^4= \begin{pmatrix} 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{pmatrix}
R4=
0401441400242200000334400421440504446624027771420
- v 5 v_5 v5作为转接点，无需修改
距离矩阵：
W
5
=
(
0
6.2
∞
1.2
7.9
9.3
0.5
6.2
0
∞
5
11.7
3.1
2
∞
∞
0
∞
∞
4
1.5
1.2
5
∞
0
6.7
8.1
1.7
7.9
11.7
∞
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
)
W^5= \begin{pmatrix} 0 & 6.2 & \infin & 1.2 & 7.9 & 9.3 & 0.5 \\ 6.2 & 0 & \infin & 5 & 11.7 & 3.1 & 2 \\ \infin & \infin & 0 & \infin & \infin & 4 & 1.5 \\ 1.2 & 5 & \infin & 0 & 6.7 & 8.1 & 1.7 \\ 7.9 & 11.7 & \infin & 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{pmatrix}
W5=
06.2∞1.27.99.30.56.20∞511.73.12∞∞0∞∞41.51.25∞06.78.11.77.911.7∞6.7014.88.49.33.148.114.805.10.521.51.78.45.10
路由矩阵：
R
5
=
(
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
)
R^5= \begin{pmatrix} 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{pmatrix}
R5=
0401441400242200000334400421440504446624027771420
- v 6 v_6 v6作为转接点
距离矩阵：
W
6
=
(
0
6.2
∗
13.3
1.2
7.9
9.3
0.5
6.2
0
∗
7.1
5
11.7
3.1
2
∗
13.3
∗
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.3
3.1
4
8.1
14.8
0
5.1
0.5
2
1.5
1.7
8.4
5.1
0
)
W^6= \begin{pmatrix} 0 & 6.2 & *13.3 & 1.2 & 7.9 & 9.3 & 0.5 \\ 6.2 & 0 & *7.1 & 5 & 11.7 & 3.1 & 2 \\ *13.3 & *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.3 & 3.1 & 4 & 8.1 & 14.8 & 0 & 5.1 \\ 0.5 & 2 & 1.5 & 1.7 & 8.4 & 5.1 & 0 \end{pmatrix}
W6=
06.2∗13.31.27.99.30.56.20∗7.1511.73.12∗13.3∗7.10∗12.1∗18.841.51.25∗12.106.78.11.77.911.7∗18.86.7014.88.49.33.148.114.805.10.521.51.78.45.10
路由矩阵：
R
6
=
(
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
)
R^6= \begin{pmatrix} 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{pmatrix}
R6=
0461441406242266066334460421446504446624027771420
- v 7 v_7 v7作为转接点
距离矩阵：
W
7
=
(
0
∗
2.5
∗
2
1.2
7.9
∗
5.6
0.5
∗
2.5
0
∗
3.5
∗
3.7
∗
10.4
3.1
2
∗
2
∗
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
)
W^7= \begin{pmatrix} 0 & *2.5 & *2 & 1.2 & 7.9 & *5.6& 0.5 \\ *2.5 & 0 & *3.5 & *3.7 & *10.4 & 3.1 & 2 \\ *2 & *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 \end{pmatrix}
W7=
0∗2.5∗21.27.9∗5.60.5∗2.50∗3.5∗3.7∗10.43.12∗2∗3.50∗3.2∗9.941.51.2∗3.7∗3.206.7∗6.81.77.9∗10.4∗9.96.70∗13.58.4∗5.63.14∗6.8∗13.505.10.521.51.78.45.10
路由矩阵：
R
7
=
(
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
)
R^7= \begin{pmatrix} 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{pmatrix}
R7=
0771471707772277077334770471477507476677027771420
从
W
7
W^7
W7和
R
7
R^7
R7可以找到任何两个节点间最短径的径长和路由。
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]
"""
为开发者提供学习成长、分享交流、生态实践、资源工具等服务，帮助开发者快速成长。
更多推荐
19
0- 0
已为社区贡献2条内容
所有评论(0)