已知图 G = ( V , E ) G=(V,E) G=(V,E),将其节点集分为两组:置定节点集 G p G_p Gp和未置定节点集 G − G p G-G_p G−Gp。其中 G p G_p Gp内的所有置定节点,是指定点 v s v_s vs到这些节点的路径为最短(即已完成最短路径的计算)的节点。而 G − G p G-G_p G−Gp内的节点是未置定节点,即 v s v_s vs到未置定节点距离是暂时的,随着算法的下一步将进行不断调整,使其成为最短径。
在调整各未置定节点的最短径时,是将 G p G_p Gp中的节点作为转接点。具体地说,就是将 G p G_p Gp中的节点作为转接点,计算 ( v s , v j ) (v_s ,v_j) (vs,vj)的径长 ( v j ∈ G − G p ) (v_jin G-G_p) (vj∈G−Gp),若该次计算的径长小于上次的值,则更新径长,否则,径长不变。计算后取其中径长最短者,之后将 v j v_j vj划归到 G p G_p Gp中。当 ( G − G p ) (G-G_p) (G−Gp)最终成为空集,同时 G p = G G_p=G Gp=G,即求得 v s v_s vs到所有其他节点的最短路径。
2.举例如图
首先写出它的邻接矩阵,由于默认不考虑自环(即一个点有一条路径连接自己)的情况,所以规定一个点到它自己的距离为0,同时规定两个点之间如果无法直接到达则距离为
∞
infin
∞
(
0
2
5
1
∞
∞
2
0
3
2
∞
∞
5
3
0
3
1
5
1
2
3
0
1
∞
∞
∞
1
1
0
2
∞
∞
5
∞
2
0
)
begin{pmatrix} 0 & 2 & 5 & 1 & infin & infin \ 2 & 0 & 3 & 2 & infin & infin \ 5 & 3 & 0 & 3 & 1 & 5 \ 1 & 2 & 3 & 0 & 1 & infin \ infin & infin & 1 & 1 & 0 & 2 \ infin & infin & 5 & infin & 2 & 0 end{pmatrix}
⎝⎜⎜⎜⎜⎜⎜⎛0251∞∞2032∞∞53031512301∞∞∞1102∞∞5∞20⎠⎟⎟⎟⎟⎟⎟⎞
现计算节点
v
1
v_1
v1到其他节点的最短路径
初始时,置定节点集 G = { } G={} G={},未置定节点集 G − G P = { v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } G-G_P={v_1,v_2,v_3,v_4,v_5,v_6} G−GP={v1,v2,v3,v4,v5,v6}
先用一张表格总览一下整个迭代过程
| 迭代次数 | v 1 , v 2 , v 3 , v 4 , v 5 , v 6 v_1,v_2,v_3,v_4,v_5,v_6 v1,v2,v3,v4,v5,v6 | 置定节点 | w i w_i wi | G p G_p Gp |
|---|---|---|---|---|
| 0 | ( 0 2 5 1 ∞ ∞ ) begin{pmatrix}0 & 2 & 5 & 1 & infin & infinend{pmatrix} (0251∞∞) | v 1 v_1 v1 | w 1 = 0 w_1=0 w1=0 | { v 1 } {v_1} {v1} |
| 1 | ( 2 5 1 ∞ ∞ ) begin{pmatrix}& & 2 & 5 & 1 & infin & infinend{pmatrix} (251∞∞) | v 4 v_4 v4 | w 4 = 1 w_4=1 w4=1 | { v 1 , v 4 } {v_1,v_4} {v1,v4} |
| 2 | ( 2 4 2 ∞ ) begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix} (242∞) | v 2 v_2 v2 | w 2 = 2 w_2=2 w2=2 | { v 1 , v 4 , v 2 } {v_1,v_4,v_2} {v1,v4,v2} |
| 3 | ( 4 2 ∞ ) begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix} (42∞) | v 5 v_5 v5 | w 5 = 2 w_5=2 w5=2 | { v 1 , v 4 , v 2 , v 5 } {v_1,v_4,v_2,v_5} {v1,v4,v2,v5} |
| 4 | ( 3 4 ) begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix} (34) | v 3 v_3 v3 | w 3 = 3 w_3=3 w3=3 | { v 1 , v 4 , v 2 , v 5 , v 3 } {v_1,v_4,v_2,v_5,v_3} {v1,v4,v2,v5,v3} |
| 5 | ( 4 ) begin{pmatrix}& & & & & & & & & & 4end{pmatrix} (4) | v 6 v_6 v6 | w 6 = 4 w_6=4 w6=4 | { v 1 , v 4 , v 2 , v 5 , v 3 , v 6 } {v_1,v_4,v_2,v_5,v_3,v_6} {v1,v4,v2,v5,v3,v6} |
具体过程描述如下:
- 第0次迭代:
(
0
2
5
1
∞
∞
)
begin{pmatrix}0 & 2 & 5 & 1 & infin & infinend{pmatrix}
(0251∞∞)
- 看矩阵的第一行,它表示节点 v 1 v_1 v1到其他节点的距离,选择其中最小的一个。
- 显然 v 1 v_1 v1到自身距离最短,为0。所以把 v 1 v_1 v1加入置定节点集,同时移出未置定节点集, G p = { v 1 } G_p={v_1} Gp={v1}, G − G P = { v 2 , v 3 , v 4 , v 5 , v 6 } G-G_P={v_2,v_3,v_4,v_5,v_6} G−GP={v2,v3,v4,v5,v6},并记录下 v 1 v_1 v1到 v 1 v_1 v1的距离 w 1 = 0 w_1=0 w1=0
- 第1次迭代:
(
2
5
1
∞
∞
)
begin{pmatrix}& & 2 & 5 & 1 & infin & infinend{pmatrix}
(251∞∞)
- 由于 G p = { v 1 } G_p={v_1} Gp={v1},只有一个节点 v 1 v_1 v1,还是看第一行,但去掉第一列,找最小的数。
- 显然是 v 1 v_1 v1到 v 4 v_4 v4距离最小, w 4 = 1 w_4=1 w4=1。所以把 v 4 v_4 v4加入置定节点集,同时移出未置定节点集,此时 G p = { v 1 , v 4 } G_p={v_1,v_4} Gp={v1,v4}, G − G P = { v 2 , v 3 , v 5 , v 6 } G-G_P={v_2,v_3,v_5,v_6} G−GP={v2,v3,v5,v6}
- 由于我们的
G
p
G_p
Gp中多了一个节点,也就是说在考虑
v
1
v_1
v1到其他节点距离时有了一个中转点
v
4
v_4
v4,那么
v
1
v_1
v1到其他节点的距离可能会因为这个
v
4
v_4
v4的存在而缩短,或者原来
v
1
v_1
v1无法直接到达的点现在可以经过
v
4
v_4
v4来到达。
- 原来 v 1 v_1 v1到 v 2 v_2 v2的距离是2,如果经过 v 4 v_4 v4再到 v 2 v_2 v2距离是4,没有变小,所以不用改;
- 原来 v 1 v_1 v1到 v 3 v_3 v3的距离是5,如果经过 v 4 v_4 v4再到 v 3 v_3 v3距离是4( v 1 v_1 v1到 v 4 v_4 v4的距离是1, v 4 v_4 v4再到 v 3 v_3 v3的距离是3)比原来的小了,需要修改;
- 原来 v 1 v_1 v1无法到达 v 5 v_5 v5,但经过 v 4 v_4 v4后可以到达,距离为2,需修改:
- 原来 v 1 v_1 v1无法到达 v 6 v_6 v6,经过 v 4 v_4 v4仍无法到达,不用改
- 至此, v 1 v_1 v1到其他节点的距离被更新为 ( 2 4 2 ∞ ) begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix} (242∞)
- 第2次迭代:
(
2
4
2
∞
)
begin{pmatrix}& & 2 & 4 & & & 2 & infinend{pmatrix}
(242∞)
- 此时 G p = { v 1 , v 4 } G_p={v_1,v_4} Gp={v1,v4},找最小的数
- 到 v 2 v_2 v2距离最小, w 2 = 2 w_2=2 w2=2,把 v 2 v_2 v2加入置定节点集,同时移出未置定节点集,此时 G p = { v 1 , v 4 , v 2 } G_p={v_1,v_4,v_2} Gp={v1,v4,v2}, G − G P = { v 3 , v 5 , v 6 } G-G_P={v_3,v_5,v_6} G−GP={v3,v5,v6}
- 此时我们又多了一个中转点
v
2
v_2
v2
- 原来 v 1 v_1 v1到 v 3 v_3 v3距离是4,经过 v 2 v_2 v2中转后距离是5,没有变小,不用改;
- 原来 v 1 v_1 v1到 v 5 v_5 v5距离是2, v 2 v_2 v2无法中转,不用改;
- 原来 v 1 v_1 v1无法到达 v 6 v_6 v6,经过 v 2 v_2 v2仍无法到达,不用改
- 至此, v 1 v_1 v1到其他节点的距离更新(其实完全没有更新)为 ( 4 2 ∞ ) begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix} (42∞)
- 第3次迭代:
(
4
2
∞
)
begin{pmatrix}& & & & 4 & & & 2 & infinend{pmatrix}
(42∞)
- 找最小
- 到 v 5 v_5 v5最小, w 5 = 2 w_5=2 w5=2, G p = { v 1 , v 4 , v 2 , v 5 } G_p={v_1,v_4,v_2,v_5} Gp={v1,v4,v2,v5}, G − G P = { v 3 , v 6 } G-G_P={v_3,v_6} G−GP={v3,v6}
- 又多了一个中转点
v
5
v_5
v5
- 原来 v 1 v_1 v1到 v 3 v_3 v3距离是4,经过 v 5 v_5 v5中转后距离是3,变小了,需要修改;
- 原来 v 1 v_1 v1无法到达 v 6 v_6 v6,经过 v 5 v_5 v5后距离变成4,修改
- 至此, v 1 v_1 v1到其他节点的距离更新为 ( 3 4 ) begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix} (34)
- 第4次迭代:
(
3
4
)
begin{pmatrix}& & & & 3 & & & & & 4end{pmatrix}
(34)
- 找最小
- 到 v 3 v_3 v3最小, w 3 = 3 w_3=3 w3=3, G p = { v 1 , v 4 , v 2 , v 5 , v 3 } G_p={v_1,v_4,v_2,v_5,v_3} Gp={v1,v4,v2,v5,v3}, G − G P = { v 6 } G-G_P={v_6} G−GP={v6}
- 又多了一个中转点
v
3
v_3
v3
- 原来 v 1 v_1 v1到 v 6 v_6 v6距离是4,经过 v 3 v_3 v3中转后距离是8,没有变小,不用修改
- 至此, v 1 v_1 v1到其他节点距离更新为 ( 4 ) begin{pmatrix}& & & & & & & & & & 4end{pmatrix} (4)
- 第5次迭代:
(
4
)
begin{pmatrix}& & & & & & & & & & 4end{pmatrix}
(4)
- 找最小
- w 6 = 4 w_6=4 w6=4, G p = { v 1 , v 4 , v 2 , v 5 , v 3 , v 6 } G_p={v_1,v_4,v_2,v_5,v_3,v_6} Gp={v1,v4,v2,v5,v3,v6}, G − G P = { } G-G_P={} G−GP={}
- G − G P G-G_P G−GP空了,说明找完了,迭代结束
结果如下表所示
| 节点 | v 1 v_1 v1 | v 2 v_2 v2 | v 3 v_3 v3 | v 4 v_4 v4 | v 5 v_5 v5 | v 6 v_6 v6 |
|---|---|---|---|---|---|---|
| 最短路径 | { v 1 } {v_1} {v1} | { v 1 , v 2 } {v_1,v_2} {v1,v2} | { v 1 , v 4 , v 5 , v 3 } {v_1,v_4,v_5,v_3} {v1,v4,v5,v3} | { v 1 , v 4 } {v_1,v_4} {v1,v4} | { v 1 , v 4 , v 5 } {v_1,v_4,v_5} {v1,v4,v5} | { v 1 , v 4 , v 5 , v 6 } {v_1,v_4,v_5,v_6} {v1,v4,v5,v6} |
| 径长 | 0 | 2 | 3 | 1 | 2 | 4 |
实现代码:
import copy
# 首先给出邻接矩阵,两个节点之间距离无穷大用-1表示
matrix = [[0, 2, 5, 1, -1, -1],
[2, 0, 3, 2, -1, -1],
[5, 3, 0, 3, 1, 5],
[1, 2, 3, 0, 1, -1],
[-1, -1, 1, 1, 0, 2],
[-1, -1, 5, -1, 2, 0]]
def dijkstra(adjacent_matrix):
# 获取节点数
node_number = len(adjacent_matrix)
# 置定节点集
G_p = []
# 未置定节点集
g_p = []
# 全部的节点集,用数字表示节点
G = []
for i in range(node_number):
G.append(i + 1)
g_p.append(i + 1)
# 用一个一维数组表示v_s节点到其他结点的距离,初始时,这个距离就是邻接矩阵的第s行
s = 1
distance = copy.deepcopy(adjacent_matrix[s - 1])
# 记录路径和径长
path = []
w = copy.deepcopy(adjacent_matrix[s - 1])
# 由于从v_s结点开始,路径的起点都是v_s
for i in range(node_number):
path.append([s])
# 开始迭代
for i in range(node_number):
# 遍历整个列表,找最小值,初始时假定最小值为最大值
min_value = max(distance)
min_index = distance.index(min_value)
for j in range(len(distance)):
if 0 <= distance[j] < min_value:
min_value = distance[j]
min_index = j
# 找到索引为min_index的节点是到v_s距离最短的,把他加入G_p中,并从g_p中移除,同时记录下最短距离
G_p.append(min_index + 1)
g_p.remove(min_index + 1)
w[min_index] = min_value
# -2表示这个点已经被选过了
distance[min_index] = -2
# 更新G_p后,需要对distance进行更新
# 对distance中的每一个数据,当添入新节点后是否有变化
# 只需考虑g_p中的节点即可
for j in g_p:
# 如果索引为min_index的节点可以到达v_j,并且从v_s到min_value再到v_j的距离比原来从v_s到v_j的距离要小
# 或者原来v_s无法到达v_j
if adjacent_matrix[min_index][j-1] > 0 and (
adjacent_matrix[min_index][j-1] + min_value < distance[j-1]
or distance[j-1] == -1):
distance[j-1] = adjacent_matrix[min_index][j-1] + min_value
for item in path[min_index]:
path[j-1].append(item)
path[j-1] = list(set(path[j-1]))
path[j-1].append(min_index+1)
print("第%d次迭代:" % i, distance, path, w)
dijkstra(matrix)
代码输出结果如下:
''' 迭代次数:[节点选择情况] [最短路径] [所选节点到每个节点的最小距离] 第0次迭代: [-2, 2, 5, 1, -1, -1] [[1], [1], [1], [1], [1], [1]] [0, 2, 5, 1, -1, -1] 第1次迭代: [-2, 2, 4, -2, 2, -1] [[1], [1], [1, 4], [1], [1, 4], [1]] [0, 2, 5, 1, -1, -1] 第2次迭代: [-2, -2, 4, -2, 2, -1] [[1], [1], [1, 4], [1], [1, 4], [1]] [0, 2, 5, 1, -1, -1] 第3次迭代: [-2, -2, 3, -2, -2, 4] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 5, 1, 2, -1] 第4次迭代: [-2, -2, -2, -2, -2, 4] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 3, 1, 2, -1] 第5次迭代: [-2, -2, -2, -2, -2, -2] [[1], [1], [1, 4, 5], [1], [1, 4], [1, 4, 5]] [0, 2, 3, 1, 2, 4] '''



