算法使用距离矩阵和路由矩阵。
距离矩阵是一个 n × n n times n n×n矩阵，以图 G G G的 n n n个节点为行和列。记为 W = [ w i j ] n × n W=[w_{ij}]_{ntimes 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 ntimes n n×n矩阵，以图 G G G的 n n n个节点为行和列。记为 R = [ r i j ] n × n R =[r_{ij}]_{ntimes 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}]_{ntimes 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}]_{ntimes 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}
- 循环变量 k k k初始值为1
- 以 k k k为中间节点时，求第 k k k次修改距离矩阵 W k = [ w i j k ] n × n W^k=[w^k_{ij}]_{ntimes 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}]_{ntimes 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
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞ 并由此得出初始路由矩阵： 于是得到： 距离矩阵： 距离矩阵： 距离矩阵： 距离矩阵： 距离矩阵： 距离矩阵：
3.举个例子
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；…………
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞(∗标注修改的值)
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞(∗标注修改的值)
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞
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
7
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 & 7 \ 4 & 7 & 7 & 4 & 0 & 7 & 4 \ 7 & 2 & 3 & 7 & 7 & 0 & 2 \ 1 & 2 & 3 & 1 & 4 & 2 & 0 \ end{pmatrix}
R7=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎛0771471707772277077334770471477507476677027777420⎠⎟⎟⎟⎟⎟⎟⎟⎟⎞
从
W
7
W^7
W7和
R
7
R^7
R7可以找到任何两个节点间最短径的径长和路由。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]
"""
