- 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} d\left(v_{i}\right)=W\left(v_{1}, v_{i}\right), &\text{若} v_{i} v_{1} \text{相邻} \ d\left(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 :
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} d\left(v_{l}\right)+W\left(v_{l}, v_{i}\right) &\text { 若 } d\left(v_{1}\right)+W\left(v_{i}, v_{i}\right)
- Step 4：重复 (2) 和 (3)，直到 v n v_n vn 改为 P P P 标号为止。
求无向图最短路
- Step 1:
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(∞} - Step 2:
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(∞)} - Step 3:
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(∞)} - Step 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 ) } 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)} - Step 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=\{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)} - Step 6:
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 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
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)
求有向图最短路
仿照上例
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 & 2\left(v_{2}\right) \text { 第1短 } \ \operatorname{Step} 2 & & 4 & 3 & \infty & 9 & \infty & 3\left(v_{4}\right) \text { 第2短 } \ \operatorname{Step} 3 & & 4 & & 8 & 9 & \infty & 4\left(v_{3}\right) \text { 第3短 } \ \text {Step } 4 & & & & 7 & 9 & \infty & 7\left(v_{5}\right) \text { 第4短 } \ \text {Step } 5 & & & & & 8 & 14 & 8\left(v_{6}\right) \text { 第5短 } \ \text {Step } 6 & & & & & & 13 & 13\left(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短
Python 实现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)<n:
i= temp.index(min(temp)) #找最小权值的节点的坐标
temp[i]=np.inf
for j in range(n):
if j not in visited:
if (dis[i]+ matr[i][j])<dis[j]:
dis[j] = temp[j] =dis[i]+ matr[i][j]
parent[j]=i #说明父节点是i
visited.append(i) #该索引已经处理了
path=[] #用于画路径
path.append(str(i))
k=i
while(parent[k]!=start): #找该节点的父节点添加到path，直到父节点是start
path.append(str(parent[k]))
k=parent[k]
path.append(str(start))
path.reverse() #path反序产生路径
print(str(i)+':','->'.join(path)) #打印路径
return dis
要求每对顶点间的最短路, 可多次使用 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 的最短路径长度.
计算时用迭代公式
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)),
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) 初始时
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), 否则.
直到迭代到 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}, j\right)=q_{1}, r_{n}\left(q_{1}, j\right)=q_{2}, \cdots, r_{n}\left(q_{t}, j\right)=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:
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
迭代 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 的两种方式中, 最短路线的距离
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⎦⎥⎥⎥⎥⎥⎥⎤
迭代 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 的所有方式中, 最短路线的距离
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⎦⎥⎥⎥⎥⎥⎥⎤
迭代 3:
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⎦⎥⎥⎥⎥⎥⎥⎤
迭代 4:
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⎦⎥⎥⎥⎥⎥⎥⎤
迭代 5:
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⎦⎥⎥⎥⎥⎥⎥⎤
迭代 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⎦⎥⎥⎥⎥⎥⎥⎤
Python 实现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 为路由矩阵
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）