- Dijkstra 算法 (求固定起点到其余各点的最短路)
- 步骤
- 示例
- Python 实现
- Floyd 算法 (求每对顶点间的最短路算法)
- 迭代方式
- 路由矩阵
- 查找最短路径
- 示例
- Python 实现
Dijkstra 算法时寻求从一固定起点 u 0 u_{0} u0 到其余各点的最短路最有效的算法之一, 由 E. W. Dijkstra 于 1959 年提出.
Dijkstra 算法的理论依据是一个重要而明显的性质: 最短路是一条路, 最短路上的任一子段也是最短路.
Dijkstra 算法的基本思想是：按距固定起点 u 0 u_{0} u0 从近到远为顺序, 依次求 得 u 0 u_{0} u0 到图 G G G 各顶点的最短路和距离, 直至某个顶点 v 0 v_{0} v0 (或直至图 G G G 的所有顶点).
步骤设图 G G G 有 n n n 个顶点; 边的长度 ℓ i j ⩾ 0 ell_{i j} geqslant 0 ℓij⩾0; 若结点 v i v_i vi 和 v j v_j vj 不相连, 则令 ℓ i j = ∞ ell_{ij}=infty ℓij=∞, 对每个结点 v i v_i vi, 令 ℓ i i = 0 ell_{ii}=0 ℓii=0.
将顶点集
V
V
V 分成两部分，一部分为具有
P
P
P（永久性）标号的集合，另一部分为具有
T
T
T（暂时性）标号的集合。
结点
v
v
v 的
P
P
P 标号是指从
v
1
v_1
v1 到
v
v
v 的最短路径的长度；顶点
u
u
u 的
T
T
T 标号是指从
v
1
v_1
v1 到
u
u
u 某条路径的长度。
Dijkstras 算法首先将
v
1
v_1
v1 取为
P
P
P 标号，其余结点取为
T
T
T 标号，逐步将具有
T
T
T 标号的结点改为
P
P
P 标号。当结点
v
n
v_n
vn 被改为
P
P
P 标号时，就找到一条从
v
1
v_1
v1 到
v
n
v_n
vn 的最短路径。
- Step 1: 初始化
将
v
1
{v}_{1}
v1 置为
P
{P}
P 标号,
d
(
v
1
)
=
0
,
P
=
{
v
1
}
;
∀
v
i
(
i
≠
1
)
{d}left({v}_{1}right)=0, {P}=left{{v}_{1}right}; forall {v}_{{i}}({i} neq 1)
d(v1)=0,P={v1};∀vi(i=1), 置
v
i
{v}_{{i}}
vi 为
T
{T}
T 标号, 即
T
=
V
−
P
T=V-P
T=V−P, 且
{
d
(
v
i
)
=
W
(
v
1
,
v
i
)
,
若
v
i
v
1
相邻
d
(
v
i
)
=
∞
,
否则
begin{cases} dleft(v_{i}right)=Wleft(v_{1}, v_{i}right), &text{若} v_{i} v_{1} text{相邻} \ dleft(v_{i}right)=infty, quad &text{否则} end{cases}
{d(vi)=W(v1,vi),d(vi)=∞,若viv1相邻否则
- Step 2: 找最小
寻找具有最小值的 T T T 标号的结点。若为 v l v_l vl，则将 v l v_l vl 的 T T T 标号改为 P P P 标号，且 P = P ∪ { v l } ， T = T − { v l } P=P cup {v_l}，T=T-{v_l} P=P∪{vl}，T=T−{vl}。
- Step 3：修改
修改与
v
l
{v_l}
vl 相邻的结点的
T
T
T 标号的值。
∀
v
i
∈
T
forall {v_i} in {T}
∀vi∈T : 求无向图最短路 即
v
2
v
3
v
4
v
5
v
6
Step
1
1
(
v
1
)
4
∞
∞
∞
(
v
2
)
第
1
短
Step
2
3
(
v
2
)
8
6
∞
(
v
3
)
第
2
短
Step
3
8
4
(
v
3
)
∞
(
v
5
)
第
3
短
Step
4
7
(
v
5
)
10
(
v
4
)
第
4
短
Step
5
9
(
v
4
)
(
v
6
)
第
5
短
begin{array}{l|ccccc} & {v}_{2} & {v}_{3} & {v}_{4} & {v}_{5} & {v}_{6} & \ hline operatorname{Step} 1 & 1({v_{1}}) & 4 & infty & infty & infty & (v_2)第1短 \ operatorname{Step} 2 & & 3(v_2) & 8 & 6 & infty & (v_3)第2短 \ operatorname{Step} 3 & & & 8 & 4 (v_{3}) & {infty} & (v_5)第3短 \ operatorname{Step} 4 & & & 7 (v_{5}) & & 10 & (v_4)第4短 \ operatorname{Step} 5 & & & & & 9 (v_{4}) & (v_6)第5短 end{array}
Step1Step2Step3Step4Step5v21(v1)v343(v2)v4∞887(v5)v5∞64(v3)v6∞∞∞109(v4)(v2)第1短(v3)第2短(v5)第3短(v4)第4短(v6)第5短 所以
v
1
v_1
v1 到各顶点的最短路径和距离分别为: 求有向图最短路
v
2
v
3
v
4
v
5
v
6
v
7
Step
1
2
5
3
∞
∞
∞
2
(
v
2
)
第1短
Step
2
4
3
∞
9
∞
3
(
v
4
)
第2短
Step
3
4
8
9
∞
4
(
v
3
)
第3短
Step
4
7
9
∞
7
(
v
5
)
第4短
Step
5
8
14
8
(
v
6
)
第5短
Step
6
13
13
(
v
7
)
第6短
begin{array}{c|ccccccr} & {v}_{2} & {v}_{3} & {v}_{4} & {v}_{5} & {v}_{6} & {v}_{7} & \ hline operatorname{Step} 1 & 2 & 5 & 3 & infty & infty & infty & 2left(v_{2}right) text { 第1短 } \ operatorname{Step} 2 & & 4 & 3 & infty & 9 & infty & 3left(v_{4}right) text { 第2短 } \ operatorname{Step} 3 & & 4 & & 8 & 9 & infty & 4left(v_{3}right) text { 第3短 } \ text {Step } 4 & & & & 7 & 9 & infty & 7left(v_{5}right) text { 第4短 } \ text {Step } 5 & & & & & 8 & 14 & 8left(v_{6}right) text { 第5短 } \ text {Step } 6 & & & & & & 13 & 13left(v_{7}right) text { 第6短 } end{array}
Step1Step2Step3Step 4Step 5Step 6v22v3544v433v5∞∞87v6∞9998v7∞∞∞∞14132(v2) 第1短 3(v4) 第2短 4(v3) 第3短 7(v5) 第4短 8(v6) 第5短 13(v7) 第6短 要求每对顶点间的最短路, 可多次使用 Dijkstra 算法, 每次以不同的顶点作为起点, 用 Dijkstra 算法求出从该起点到其余顶点的最短路径, 反复执行
n
−
1
n-1
n−1 次这样的操作, 就可得到每对顶点之间的最短路. 但这样做需要大量的重复计算, 效率不高. R. W. Floyd 于 1962 年提出了一个直接寻求任意两顶点之间最短路的算法. Floyd 算法是一个经典的动态规划算法, 其基本思想是递推产生一个矩阵序列
A
1
,
A
2
,
⋯
,
A
k
,
⋯
,
A
n
A_{1}, A_{2}, cdots, A_{k}, cdots, A_{n}
A1,A2,⋯,Ak,⋯,An, 其中矩阵
A
k
=
(
a
k
(
i
,
j
)
)
n
×
n
A_{k}=left(a_{k}(i, j)right)_{n times n}
Ak=(ak(i,j))n×n, 其第
i
i
i 行第
j
j
j 列元素
a
k
(
i
,
j
)
a_{k}(i, j)
ak(i,j) 表示从顶点
v
i
v_{i}
vi 到顶点
v
j
v_{j}
vj 的路径上所经过的顶点序号不大于
k
k
k 的最短路径长度. 计算时用迭代公式
k
k
k 是迭代次数,
i
,
j
,
k
=
1
,
2
,
⋯
,
n
i, j, k=1,2, cdots, n
i,j,k=1,2,⋯,n.
A
0
A_0
A0 为邻接矩阵, 当
k
=
n
k=n
k=n 时,
A
n
A_{n}
An 即是各顶点之间的最短距离值. 如果在求得两点间的最短距离时, 还需要求得两点间的最短路径, 需要在上面距离矩阵
A
k
A_{k}
Ak 的迭代过程中, 引入一个路由矩阵
R
k
=
(
r
k
(
i
,
j
)
)
n
×
n
R_{k}=left(r_{k}(i, j)right)_{n times n}
Rk=(rk(i,j))n×n 来记录两点间路径的前驱后继关系, 其中
r
k
(
i
,
j
)
r_{k}(i, j)
rk(i,j) 表示从顶点
v
i
v_{i}
vi 到顶点
v
j
v_{j}
vj 的路径经过编号为
r
k
(
i
,
j
)
r_{k}(i, j)
rk(i,j) 的顶点. 路由矩阵的迭代过程如下: (1) 初始时 其中 直到迭代到
k
=
n
k=n
k=n, 算法终止. 查找
v
i
v_{i}
vi 到
v
j
v_{j}
vj 最短路径的方法如下: 若
r
n
(
i
,
j
)
=
p
1
r_{n}(i, j)=p_{1}
rn(i,j)=p1, 则点
v
p
1
v_{p_{1}}
vp1 是顶点
v
i
v_{i}
vi 到顶点
v
j
v_{j}
vj 的最短路的中间点, 然后用同样的方法再分头查找. 若 (1) 向顶点
v
i
v_{i}
vi 反向追踪得:
r
n
(
i
,
p
1
)
=
p
2
,
r
n
(
i
,
p
2
)
=
p
3
,
⋯
,
r
n
(
i
,
p
s
)
=
0
r_{n}left(i, p_{1}right)=p_{2}, r_{n}left(i, p_{2}right)=p_{3}, cdots, r_{n}left(i, p_{s}right)=0
rn(i,p1)=p2,rn(i,p2)=p3,⋯,rn(i,ps)=0; (2) 向顶点
v
j
v_{j}
vj 正向追踪得:
r
n
(
p
1
,
j
)
=
q
1
,
r
n
(
q
1
,
j
)
=
q
2
,
⋯
,
r
n
(
q
t
,
j
)
=
0
r_{n}left(p_{1}, jright)=q_{1}, r_{n}left(q_{1}, jright)=q_{2}, cdots, r_{n}left(q_{t}, jright)=0
rn(p1,j)=q1,rn(q1,j)=q2,⋯,rn(qt,j)=0; 则由点
v
i
v_{i}
vi 到
v
j
v_{j}
vj 的最短路径为:
v
i
,
v
p
s
,
⋯
,
v
p
2
,
v
p
1
,
v
q
1
,
v
q
2
,
⋯
,
v
q
t
,
v
j
v_{i}, v_{p_{s}}, cdots, v_{p_{2}}, v_{p_{1}}, v_{q_{1}}, v_{q_{2}}, cdots, v_{q_{t}}, v_{j}
vi,vps,⋯,vp2,vp1,vq1,vq2,⋯,vqt,vj. 迭代 0: 迭代 1:
A
1
A_1
A1 的元素
a
(
i
,
j
)
a(i, j)
a(i,j) 的意义为
i
i
i 直接到达
j
j
j 及经节点 1 到达
j
{j}
j 的两种方式中, 最短路线的距离 迭代 2:
A
2
A_2
A2 的元素
a
(
i
,
j
)
a(i, j)
a(i,j) 的意义为
i
i
i 直接到达
j
j
j 及最多经节点 1, 2 到达
j
{j}
j 的所有方式中, 最短路线的距离 迭代 3: 迭代 4: 迭代 5: 迭代 6 (
n
n
n): 任意两节点之间的最短路, 最多可经过节点
1
、
2
…
n
1 、 2 ldots n
1、2…n 到达, 因此当迭代
n
{n}
n 次时, 算法结束, 得到任意两点间的最短路及其距离.如本例题中, 节点
1
,
6
1, 6
1,6 之间的最短路为
1
−
2
−
4
−
6
1-2-4-6
1−2−4−6, 距离为
9
9
9; 节点
3
,
4
3, 4
3,4 之间的最短路为
3
−
5
−
4
3-5-4
3−5−4, 距离为
3
3
3; 节点
6
,
4
6, 4
6,4 之间的最短路为
6
−
4
6-4
6−4, 距离为
3
3
3 , 等等.
A
6
=
[
0
4
6
6
124
5
125
9
1246
4
0
2
2
1
5
246
6
2
0
3
354
2
6
3546
6
421
2
3
453
0
1
3
5
521
1
2
1
0
4
546
9
6421
5
642
6
6453
3
4
645
0
]
,
R
6
=
[
0
0
0
2
2
4
0
0
0
0
0
4
0
0
0
5
0
5
2
0
5
0
0
0
2
0
0
0
0
4
4
4
5
0
4
0
]
mathrm{A}_{6}=left[begin{array}{c} 0 & 4 & 6 & 6_{124} & 5_{125} & 9_{1246} \ 4 & 0 & 2 & 2 & 1 & 5_{246} \ 6 & 2 & 0 & 3_{354} & 2 & 6_{3546} \ 6_{421} & 2 & 3_{453} & 0 & 1 & 3 \ 5_{521} & 1 & 2 & 1 & 0 & 4_{546} \ 9_{6421} & 5_{642} & 6_{6453} & 3 & 4_{645} & 0 end{array}right], {R}_{6}=left[begin{array}{c} 0 & 0 & 0 & 2 & 2 & 4 \ 0 & 0 & 0 & 0 & 0 & 4 \ 0 & 0 & 0 & 5 & 0 & 5 \ 2 & 0 & 5 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 & 0 & 4 \ 4 & 4 & 5 & 0 & 4 & 0 end{array}right]
A6=⎣⎢⎢⎢⎢⎢⎢⎡0466421552196421402215642620345326645361242335401351251210464591246524663546345460⎦⎥⎥⎥⎥⎥⎥⎤,R6=⎣⎢⎢⎢⎢⎢⎢⎡000224000004000505205000200004445040⎦⎥⎥⎥⎥⎥⎥⎤
d
(
v
i
)
=
{
d
(
v
l
)
+
W
(
v
l
,
v
i
)
若
d
(
v
1
)
+
W
(
v
i
,
v
i
)
<
d
(
v
i
)
d
(
v
i
)
否则
d(v_i)=left{begin{array}{ll} dleft(v_{l}right)+Wleft(v_{l}, v_{i}right) &text { 若 } dleft(v_{1}right)+Wleft(v_{i}, v_{i}right)
示例
P
=
{
v
1
(
0
)
}
P={v_1(0)}
P={v1(0)}
T
=
{
v
2
(
1
,
v
1
)
,
v
3
(
4
,
v
1
)
,
v
4
(
∞
)
,
v
5
(
∞
)
,
v
6
(
∞
}
T={v_2(1,v_1),v_3(4,v_1),v_4(infty),v_5(infty),v_6(infty}
T={v2(1,v1),v3(4,v1),v4(∞),v5(∞),v6(∞}
P
=
{
v
1
(
0
)
,
v
2
(
1
,
v
1
)
}
P={v_1(0),v_2(1,v_1)}
P={v1(0),v2(1,v1)}
T
=
{
v
3
(
3
,
v
1
,
v
2
)
,
v
4
(
8
,
v
1
,
v
2
)
,
v
5
(
6
,
v
1
,
v
2
)
,
v
6
(
∞
)
}
T={v_3(3,v_1,v_2),v_4(8,v_1,v_2),v_5(6,v_1,v_2),v_6(infty)}
T={v3(3,v1,v2),v4(8,v1,v2),v5(6,v1,v2),v6(∞)}
P
=
{
v
1
(
0
)
,
v
2
(
1
,
v
1
)
,
v
3
(
3
,
v
1
,
v
2
)
}
P={v_1(0),v_2(1,v_1) , v_3(3,v_1,v_2)}
P={v1(0),v2(1,v1),v3(3,v1,v2)}
T
=
{
v
4
(
8
,
v
1
,
v
2
)
,
v
5
(
4
,
v
1
,
v
2
,
v
3
)
,
v
6
(
∞
)
}
T={v_4(8,v_1,v_2),v_5(4,v_1,v_2,v_3),v_6(infty)}
T={v4(8,v1,v2),v5(4,v1,v2,v3),v6(∞)}
P
=
{
v
1
(
0
)
,
v
2
(
1
,
v
1
)
,
v
3
(
3
,
v
1
,
v
2
)
,
v
5
(
4
,
v
1
,
v
2
,
v
3
)
}
P={v_1(0),v_2(1,v_1) , v_3(3,v_1,v_2),v_5(4,v_1,v_2,v_3)}
P={v1(0),v2(1,v1),v3(3,v1,v2),v5(4,v1,v2,v3)}
T
=
{
v
4
(
7
,
v
1
,
v
2
,
v
3
,
v
5
)
,
v
6
(
10
,
v
1
,
v
2
,
v
3
,
v
5
)
}
T={v_4(7,v_1,v_2,v_3,v_5),v_6(10,v_1,v_2,v_3,v_5)}
T={v4(7,v1,v2,v3,v5),v6(10,v1,v2,v3,v5)}
P
=
{
v
1
(
0
)
,
v
2
(
1
,
v
1
)
,
v
3
(
3
,
v
1
,
v
2
)
,
v
5
(
4
,
v
1
,
v
2
,
v
3
)
,
v
4
(
7
,
v
1
,
v
2
,
v
3
,
v
5
)
}
P={v_1(0),v_2(1,v_1) , v_3(3,v_1,v_2),v_5(4,v_1,v_2,v_3),v_4(7,v_1,v_2,v_3,v_5)}
P={v1(0),v2(1,v1),v3(3,v1,v2),v5(4,v1,v2,v3),v4(7,v1,v2,v3,v5)}
T
=
{
v
6
(
9
,
v
1
,
v
2
,
v
3
,
v
5
,
v
4
)
}
T={v_6(9,v_1,v_2,v_3,v_5,v_4)}
T={v6(9,v1,v2,v3,v5,v4)}
P
=
{
v
1
(
0
)
,
v
2
(
1
,
v
1
)
,
v
3
(
3
,
v
1
,
v
2
)
,
v
5
(
4
,
v
1
,
v
2
,
v
3
)
,
v
4
(
7
,
v
1
,
v
2
,
v
3
,
v
5
)
,
v
6
(
9
,
v
1
,
v
2
,
v
3
,
v
5
,
v
4
)
}
P={v_1(0),v_2(1,v_1) , v_3(3,v_1,v_2),v_5(4,v_1,v_2,v_3),v_4(7,v_1,v_2,v_3,v_5),v_6(9,v_1,v_2,v_3,v_5,v_4)}
P={v1(0),v2(1,v1),v3(3,v1,v2),v5(4,v1,v2,v3),v4(7,v1,v2,v3,v5),v6(9,v1,v2,v3,v5,v4)}
T
=
{
}
T={}
T={}
v
2
:
v
1
→
v
2
(
1
)
v_2: v_1 rightarrow v_2 quad (1)
v2:v1→v2(1)
v
3
:
v
1
→
v
2
→
v
3
(
3
)
v_3: v_1 rightarrow v_2 rightarrow v_3 quad (3)
v3:v1→v2→v3(3)
v
5
:
v
1
→
v
2
→
v
3
→
v
5
(
4
)
v_5: v_1 rightarrow v_2 rightarrow v_3 rightarrow v_5 quad (4)
v5:v1→v2→v3→v5(4)
v
4
:
v
1
→
v
2
→
v
3
→
v
5
→
v
4
(
7
)
v_4: v_1 rightarrow v_2 rightarrow v_3 rightarrow v_5 rightarrow v_4 quad (7)
v4:v1→v2→v3→v5→v4(7)
v
6
:
v
1
→
v
2
→
v
3
→
v
5
→
v
4
→
v
6
(
9
)
v_6: v_1 rightarrow v_2 rightarrow v_3 rightarrow v_5 rightarrow v_4 rightarrow v_6 quad (9)
v6:v1→v2→v3→v5→v4→v6(9)
仿照上例import numpy as np
def Dijkstra_all_minpath(matr,start): #matr为邻接矩阵的数组，start表示起点
n=len( matr) #该图的节点数
dis=[]; temp=[]
dis.extend(matr[start]) #添加数组matr的start行元素
temp.extend(matr[start]) #添加矩阵matr的start行元素
temp[start] = np.inf #临时数组会把处理过的节点的值变成 infty
visited=[start] #start已处理
parent=[start]*n #用于画路径，记录此路径中该节点的父节点
while len(visited)
Floyd 算法 (求每对顶点间的最短路算法)
a
k
(
i
,
j
)
=
min
(
a
k
−
1
(
i
,
j
)
,
a
k
−
1
(
i
,
k
)
+
a
k
−
1
(
k
,
j
)
)
,
a_{k}(i, j)=min left(a_{k-1}(i, j), a_{k-1}(i, k)+a_{k-1}(k, j)right),
ak(i,j)=min(ak−1(i,j),ak−1(i,k)+ak−1(k,j)),
R
0
=
0
n
×
n
{R}_{0}=boldsymbol{0}_{n times n}
R0=0n×n
(2) 迭代公式为
R
k
=
(
r
k
(
i
,
j
)
)
n
×
n
,
R_{k}=left(r_{k}(i, j)right)_{n times n},
Rk=(rk(i,j))n×n,
r
k
(
i
,
j
)
=
{
k
,
若
a
k
−
1
(
i
,
j
)
>
a
k
−
1
(
i
,
k
)
+
a
k
−
1
(
k
,
j
)
,
r
k
−
1
(
i
,
j
)
,
否则.
r_{k}(i, j)=left{begin{array}{l} k, quad text { 若 } a_{k-1}(i, j)>a_{k-1}(i, k)+a_{k-1}(k, j), \ r_{k-1}(i, j), quad text { 否则. } end{array}right.
rk(i,j)={k, 若 ak−1(i,j)>ak−1(i,k)+ak−1(k,j),rk−1(i,j), 否则.
A
0
=
[
0
4
6
∞
∞
∞
4
0
2
2
1
∞
6
2
0
∞
2
∞
∞
2
∞
0
1
3
∞
1
2
1
0
7
∞
∞
∞
3
7
0
]
,
R
0
=
(
0
)
6
×
6
A_{0}=left[begin{array}{c} 0 & 4 & 6 & infty & infty & infty \ 4 & 0 & 2 & 2 & 1 & infty \ 6 & 2 & 0 & infty & 2 & infty \ infty & 2 & infty & 0 & 1 & 3 \ infty & 1 & 2 & 1 & 0 & 7 \ infty & infty & infty & 3 & 7 & 0 end{array}right], {R}_{0}=(0)_{6 times 6}
A0=⎣⎢⎢⎢⎢⎢⎢⎡046∞∞∞40221∞620∞2∞∞2∞013∞12107∞∞∞370⎦⎥⎥⎥⎥⎥⎥⎤,R0=(0)6×6
A
1
=
[
0
4
6
∞
∞
∞
4
0
2
2
1
∞
6
2
0
∞
2
∞
∞
2
∞
0
1
3
∞
1
2
1
0
7
∞
∞
∞
3
7
0
]
,
R
1
=
[
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
]
mathrm{A}_{1}=left[begin{array}{c} 0 & 4 & 6 & infty & infty & infty \ 4 & 0 & 2 & 2 & 1 & infty \ 6 & 2 & 0 & infty & 2 & infty \ infty & 2 & infty & 0 & 1 & 3 \ infty & 1 & 2 & 1 & 0 & 7 \ infty & infty & infty & 3 & 7 & 0 end{array}right] , {R}_{1}=left[begin{array}{c} 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 end{array}right]
A1=⎣⎢⎢⎢⎢⎢⎢⎡046∞∞∞40221∞620∞2∞∞2∞013∞12107∞∞∞370⎦⎥⎥⎥⎥⎥⎥⎤,R1=⎣⎢⎢⎢⎢⎢⎢⎡000000000000000000000000000000000000⎦⎥⎥⎥⎥⎥⎥⎤
A
2
=
[
0
4
6
6
5
∞
4
0
2
2
1
∞
6
2
0
4
2
∞
6
2
4
0
1
3
5
1
2
1
0
7
∞
∞
∞
3
7
0
]
,
R
2
=
[
0
0
0
2
2
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
2
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
]
A_{2}=left[begin{array}{c} 0 & 4 & 6 & 6 & 5 & infty \ 4 & 0 & 2 & 2 & 1 & infty \ 6 & 2 & 0 & 4 & 2 & infty \ 6 & 2 & 4 & 0 & 1 & 3 \ 5 & 1 & 2 & 1 & 0 & 7 \ infty & infty & infty & 3 & 7 & 0 end{array}right], R_{2}=left[begin{array}{c} 0 & 0 & 0 & 2 & 2 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 2 & 0 & 0 \ 2 & 0 & 2 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 end{array}right]
A2=⎣⎢⎢⎢⎢⎢⎢⎡04665∞40221∞62042∞624013512107∞∞∞370⎦⎥⎥⎥⎥⎥⎥⎤,R2=⎣⎢⎢⎢⎢⎢⎢⎡000220000000000200202000200000000000⎦⎥⎥⎥⎥⎥⎥⎤
A
3
=
[
0
4
6
6
5
∞
4
0
2
2
1
∞
6
2
0
4
2
∞
6
2
4
0
1
3
5
1
2
1
0
7
∞
∞
∞
3
7
0
]
,
R
3
=
[
0
0
0
2
2
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
2
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
]
mathrm{A}_{3}=left[begin{array}{c} 0 & 4 & 6 & 6 & 5 & infty \ 4 & 0 & 2 & 2 & 1 & infty \ 6 & 2 & 0 & 4 & 2 & infty \ 6 & 2 & 4 & 0 & 1 & 3 \ 5 & 1 & 2 & 1 & 0 & 7 \ infty & infty & infty & 3 & 7 & 0 end{array}right], {R}_{3}=left[begin{array}{c} 0 & 0 & 0 & 2 & 2 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 2 & 0 & 0 \ 2 & 0 & 2 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 end{array}right]
A3=⎣⎢⎢⎢⎢⎢⎢⎡04665∞40221∞62042∞624013512107∞∞∞370⎦⎥⎥⎥⎥⎥⎥⎤,R3=⎣⎢⎢⎢⎢⎢⎢⎡000220000000000200202000200000000000⎦⎥⎥⎥⎥⎥⎥⎤
A
4
=
[
0
4
6
6
5
9
4
0
2
2
1
5
6
2
0
4
2
7
6
2
4
0
1
3
5
1
2
1
0
4
9
5
7
3
4
0
]
,
R
4
=
[
0
0
0
2
2
4
0
0
0
0
0
4
0
0
0
2
0
4
2
0
2
0
0
0
2
0
0
0
0
4
4
4
4
0
4
0
]
mathrm{A}_{4}=left[begin{array}{c} 0 & 4 & 6 & 6 & 5 & 9 \ 4 & 0 & 2 & 2 & 1 & 5 \ 6 & 2 & 0 & 4 & 2 & 7 \ 6 & 2 & 4 & 0 & 1 & 3 \ 5 & 1 & 2 & 1 & 0 & 4 \ 9 & 5 & 7 & 3 & 4 & 0 end{array}right], {R}_{4}=left[begin{array}{c} 0 & 0 & 0 & 2 & 2 & 4 \ 0 & 0 & 0 & 0 & 0 & 4 \ 0 & 0 & 0 & 2 & 0 & 4 \ 2 & 0 & 2 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 & 0 & 4 \ 4 & 4 & 4 & 0 & 4 & 0 end{array}right]
A4=⎣⎢⎢⎢⎢⎢⎢⎡046659402215620427624013512104957340⎦⎥⎥⎥⎥⎥⎥⎤,R4=⎣⎢⎢⎢⎢⎢⎢⎡000224000004000204202000200004444040⎦⎥⎥⎥⎥⎥⎥⎤
A
5
=
[
0
4
6
6
5
9
4
0
2
2
1
5
6
2
0
3
2
6
6
2
3
0
1
3
5
1
2
1
0
4
9
5
6
3
4
0
]
,
R
5
=
[
0
0
0
2
2
4
0
0
0
0
0
4
0
0
0
5
0
5
2
0
5
0
0
0
2
0
0
0
0
4
4
4
5
0
4
0
]
mathrm{A}_{5}=left[begin{array}{c} 0 & 4 & 6 & 6 & 5 & 9 \ 4 & 0 & 2 & 2 & 1 & 5 \ 6 & 2 & 0 & 3 & 2 & 6 \ 6 & 2 & 3 & 0 & 1 & 3 \ 5 & 1 & 2 & 1 & 0 & 4 \ 9 & 5 & 6 & 3 & 4 & 0 end{array}right], {R}_{5}=left[begin{array}{c} 0 & 0 & 0 & 2 & 2 & 4 \ 0 & 0 & 0 & 0 & 0 & 4 \ 0 & 0 & 0 & 5 & 0 & 5 \ 2 & 0 & 5 & 0 & 0 & 0 \ 2 & 0 & 0 & 0 & 0 & 4 \ 4 & 4 & 5 & 0 & 4 & 0 end{array}right]
A5=⎣⎢⎢⎢⎢⎢⎢⎡046659402215620326623013512104956340⎦⎥⎥⎥⎥⎥⎥⎤,R5=⎣⎢⎢⎢⎢⎢⎢⎡000224000004000505205000200004445040⎦⎥⎥⎥⎥⎥⎥⎤import numpy as np
def floyd(graph):
m = len(graph)
dis = graph
path = np.zeros((m, m)) #路由矩阵初始化
for k in range(m):
for i in range(m):
for j in range(m):
if dis[i][k] + dis[k][j] < dis[i][j]:
dis[i][j] = dis[i][k] + dis[k][j]
path[i][j] = k
return dis, path
# dis 为各顶点的最短距离矩阵
# path 为路由矩阵
