本文借鉴于张广河教授主编的《数据结构》，对其中的代码进行了完善。
从某源点到其余各顶点的最短路径
Dijkstra算法可用于求解图中某源点到其余各顶点的最短路径。假设G=｛V，｛E｝｝是含有n个顶点的有向图，以该图中顶点v为源点，使用Dijkstra算法求顶点v到图中其余各顶点的最短路径的基本思想如下：
- 使用集合S记录已求得最短路径的终点，初始时S={v}。
- 选择一条长度最小的最短路径，该路径的终点w属于V-S，将w并入S，并将该最短路径的长度记为Dw。
-
对于V-S中任一顶点是s，将源点到顶点s的最短路径长度记为Ds，并将顶点w到顶点s的弧的权值记为Dws，若Dw+Dws
则将源点到顶点s的最短路径长度修改为Dw+Ds=ws。 -
重复执行2和3，知道S=V。
为了实现算法， - 使用邻接矩阵Arcs存储有向网，当i=j时，Arcs[i][j]=0；当i!=j时，若下标为i的顶点到下标为j的顶点有弧且弧的权值为w，则Arcs[i][j]=w，否则Arcs[i][j]=float(‘inf’)即无穷大。
- 使用Dist存储源点到每一个终点的最短路径长度。
- 使用列表Path存储每一条最短路径中倒数第二个顶点的下标。
- 使用flag记录每一个顶点是否已经求得最短路径，在思想中即是判断顶点是属于V集合，还是属于V-S集合。
代码实现
#构造有向图Graph
class
Graph
:
def
__init__
(
self
,
graph
,
labels
)
:
#labels为标点名称
self
.
Arcs
=
graph
self
.
VertexNum
=
graph
.
shape
[
0
]
self
.
labels
=
labels
def
Dijkstra
(
self
,
Vertex
,
EndNode
)
:
#Vertex为源点，EndNode为终点
Dist
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#存储源点到每一个终点的最短路径的长度
Path
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#存储每一条最短路径中倒数第二个顶点的下标
flag
=
[
[
]
for
i
in
range
(
self
.
VertexNum
)
]
#记录每一个顶点是否求得最短路径
index
=
0
#初始化
while
index
<
self
.
VertexNum
:
Dist
[
index
]
=
self
.
Arcs
[
Vertex
]
[
index
]
flag
[
index
]
=
0
if
self
.
Arcs
[
Vertex
]
[
index
]
<
float
(
'inf'
)
:
#正无穷
Path
[
index
]
=
Vertex
else
:
Path
[
index
]
=
-
1
#表示从顶点Vertex到index无路径
index
+=
1
flag
[
Vertex
]
=
1
Path
[
Vertex
]
=
0
Dist
[
Vertex
]
=
0
index
=
1
while
index
<
self
.
VertexNum
:
MinDist
=
float
(
'inf'
)
j
=
0
while
j
<
self
.
VertexNum
:
if
flag
[
j
]
==
0
and
Dist
[
j
]
<
MinDist
:
tVertex
=
j
#tVertex为目前从V-S集合中找出的距离源点Vertex最断路径的顶点
MinDist
=
Dist
[
j
]
j
+=
1
flag
[
tVertex
]
=
1
EndVertex
=
0
MinDist
=
float
(
'inf'
)
#表示无穷大，若两点间的距离小于MinDist说明两点间有路径
#更新Dist列表，符合思想中第三条
while
EndVertex
<
self
.
VertexNum
:
if
flag
[
EndVertex
]
==
0
:
if
self
.
Arcs
[
tVertex
]
[
EndVertex
]
<
MinDist
and
Dist
[
tVertex
]
+
self
.
Arcs
[
tVertex
]
[
EndVertex
]
<
Dist
[
EndVertex
]
:
Dist
[
EndVertex
]
=
Dist
[
tVertex
]
+
self
.
Arcs
[
tVertex
]
[
EndVertex
]
Path
[
EndVertex
]
=
tVertex
EndVertex
+=
1
index
+=
1
vertex_endnode_path
=
[
]
#存储从源点到终点的最短路径
return
Dist
[
EndNode
]
,
start_end_Path
(
Path
,
Vertex
,
EndNode
,
vertex_endnode_path
)
#根据本文上述定义的Path递归求路径
def
start_end_Path
(
Path
,
start
,
endnode
,
path
)
:
if
start
==
endnode
:
path
.
append
(
start
)
else
:
path
.
append
(
endnode
)
start_end_Path
(
Path
,
start
,
Path
[
endnode
]
,
path
)
return
path
if
__name__
==
'__main__'
:
#float('inf')表示无穷
graph
=
np
.
array
(
[
[
0
,
6
,
5
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
0
,
2
,
8
,
float
(
'inf'
)
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
0
,
float
(
'inf'
)
,
3
,
float
(
'inf'
)
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
7
,
0
,
float
(
'inf'
)
,
9
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
0
,
9
]
,
[
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
float
(
'inf'
)
,
0
]
]
)
G
=
Graph
(
graph
,
labels
=
[
'a'
,
'b'
,
'c'
,
'd'
,
'e'
,
'f'
]
)
start
=
input
(
'请输入源点'
)
endnode
=
input
(
'请输入终点'
)
dist
,
path
=
Dijkstra
(
G
,
G
.
labels
.
index
(
start
)
,
G
.
labels
.
index
(
endnode
)
)
Path
=
[
]
for
i
in
range
(
len
(
path
)
)
:
Path
.
append
(
G
.
labels
[
path
[
len
(
path
)
-
1
-
i
]
]
)
print
(
'从顶点{}到顶点{}的最短路径为：\n{}\n最短路径长度为：{}'
.
format
(
start
,
endnode
,
Path
,
dist
)
)
输出结果如下：
请输入源点
a
请输入终点
f
从顶点a到顶点f的最短路径为：
['a', 'c', 'e', 'f']
最短路径长度为：17
