前言
本篇章主要介绍图的最短路径问题，包括Dijkstra算法和Floyd算法 ，并用Python代码实现 。
1. 创建图
在开始之前 ，我们先创建一个图，使用邻接矩阵表示有向网：
class Graph(object):
"""
以邻接矩阵为存储结构创建有向网
"""
def __init__(self, kind):
# 图的类型: 无向图, 有向图, 无向网, 有向网
# kind: Undigraph, Digraph, Undinetwork, Dinetwork,
self.kind = kind
# 顶点表
self.vertexs = []
# 边表, 即邻接矩阵, 是个二维的
self.arcs = []
# 当前顶点数
self.vexnum = 0
# 当前边(弧)数
self.arcnum = 0
def CreateGraph(self, vertex_list, edge_list):
"""
创建图
:param vertex_list: 顶点列表
:param edge_list: 边列表
:return:
"""
self.vexnum = len(vertex_list)
self.arcnum = len(edge_list)
for vertex in vertex_list:
vertex = Vertex(vertex)
# 顶点列表
self.vertexs.append(vertex)
# 邻接矩阵, 初始化为无穷
self.arcs.append([float('inf')] * self.vexnum)
for edge in edge_list:
ivertex = self.LocateVertex(edge[0])
jvertex = self.LocateVertex(edge[1])
weight = edge[2]
self.InsertArc(ivertex, jvertex, weight)
def LocateVertex(self, vertex):
"""
定位顶点在邻接表中的位置
:param vertex:
:return:
"""
index = 0
while index < self.vexnum:
if self.vertexs[index].data == vertex:
return index
else:
index += 1
def InsertArc(self, ivertex, jvertex, weight):
"""
创建邻接矩阵
:param ivertex:
:param jvertex:
:param weight:
:return:
"""
if self.kind == 'Dinetwork':
self.arcs[ivertex][jvertex] = weight
有关邻接矩阵中顶点结点
Vertex()的定义可以参考这篇博客，这里就不在贴出相应的代码了 。
2. 问题来源
假如我从城市
A
A
A出发坐火车去其他城市旅游 ，那么如何规划路线使所花费的车票钱最少呢？若将上述图中的城市看成有向网中的顶点 ，并将两城市之间所需要的车票钱看做对应弧的权值，那么这一问题的本质就是求两个顶点之间权值最小的路径 ，简称最短路径
(
S
h
o
r
t
e
s
t
(Shortest
(Shortest
P
a
t
h
)
Path)
Path)。
3. Dijkstra算法
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法 ，中文名叫迪杰斯特拉算法，它常用于求解源点到其余顶点的最短路径。
假设
G
=
{
V
,
{
A
}
}
G=\{V, \{A\}\}
G={V,{A}}是含有
n
n
n个顶点的有向网 ，以该图中的顶点
v
v
v为源点 ，使用
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法求顶点
v
v
v到图中其余各顶点的最短路径的基本思路如下：
(1) 使用集合
S
S
S记录已求得最短路径的终点，初始时
S
=
{
v
}
S=\{v\}
S={v}；
(2) 选择一条长度最短的路径 ，该路径的终点
w
∈
V
−
S
w\in V-S
w∈V−S ，将
w
w
w并入
S
S
S，并将该最短路径的长度记为
D
w
D_w
Dw；
(3) 对于
V
−
S
V-S
V−S中任一顶点
s
s
s ，将源点到顶点
s
s
s的最短路径长度记为
D
s
D_s
Ds ，并将顶点
w
w
w到顶点
s
s
s的弧的权值记为
D
w
s
D_{ws}
Dws，若
D
w
+
D
w
s
<
D
s
D_w+D_{ws}<D_s
Dw+Dws<Ds，则将源点到顶点
s
s
s的最短路径的长度修改为
D
w
+
D
w
s
D_w+D_{ws}
Dw+Dws；
(4) 重复执行上述操作 ，直到
S
=
V
S=V
S=V 。
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法有些
P
r
i
m
Prim
Prim算法的影子 ，这里使用一个辅助列表Dist，用来存储源点到每一个终点的最短路径长度 ，列表Path来存储每一条最短路径中倒数第二个顶点的下标(弧尾下标) ，除此之外还需要一个列表flag来记录顶点是否已求得最短路径 。下面结合着
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法来分析一下上面的那个有向网：
(1) 这里要做的就是更新列表Dist和列表Path，假如以顶点
A
A
A为起始点 ，先将它加入
S
S
S中 ，然后寻找以顶点
A
A
A为弧尾的最短路径，这里找到了顶点
B
B
B ，然后继续找下一个顶点。这个时候就要做一个判断了 ，即
D
w
+
D
w
s
<
D
s
D_w+D_{ws}<D_s
Dw+Dws<Ds是否成立，这里的顶点
s
s
s有两种选择 ，要么是顶点
C
C
C ，要么是顶点
D
D
D，因为这两个顶点都是以顶点
w
w
w(即顶点
B
B
B)为弧尾，按照顺序 ，这个时候先选择了顶点
C
C
C ，经判断：
D
A
B
+
D
B
C
<
D
A
C
D_{AB}+D_{BC}<D_{AC}
DAB+DBC<DAC(即
4
+
3
=
7
<
8
4+3=7<8
4+3=7<8)成立，然后更新源点到顶点
s
s
s(即顶点
C
C
C)的距离为7 。这个时候顶点
s
s
s又选择了顶点
D
D
D ，经判断：
D
A
B
+
D
B
D
<
D
A
D
D_{AB}+D_{BD}<D_{AD}
DAB+DBD<DAD(即
4
+
8
=
12
<
∞
4+8=12<\infty
4+8=12<∞)成立 ，然后更新源点到顶点
s
s
s(即顶点
D
D
D)的距离为12 。
(2) 然后寻找以顶点
C
C
C为弧尾的最短路径，这里找到了顶点
E
E
E ，然后做一个路径长度判断 ，经判断：
D
A
C
+
D
C
E
<
D
A
E
D_{AC}+D_{CE}<D_{AE}
DAC+DCE<DAE(即
7
+
1
=
8
<
∞
7+1=8<\infty
7+1=8<∞)成立，然后更新源点到顶点
s
s
s(即顶点
E
E
E)的距离为8 ，然后又找到了顶点
F
F
F ，然后做一个路径长度判断，经判断：
D
A
C
+
D
C
F
<
D
A
F
D_{AC}+D_{CF}<D_{AF}
DAC+DCF<DAF(即
7
+
6
=
13
<
∞
7+6=13<\infty
7+6=13<∞)成立 ，然后更新源点到顶点
s
s
s(即顶点
F
F
F)的距离为13。
(3) 直至计算出所有源点到其余顶点的距离 。
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法代码实现如下：
def Dijkstra(self, Vertex):
"""
Dijkstra算法, 计算源点Vertex到其余各顶点的最短距离
:param Vertex:
:return:
"""
# 源点到每一个终点的最短路径长度
Dist = []
# 每一条最短路径中倒数第二个顶点的下标(弧尾下标)
Path = []
# 记录顶点是否已求得最短路径
flag = [False] * self.vexnum
index = 0
while index < self.vexnum:
Dist.append(self.arcs[Vertex][index])
if self.arcs[Vertex][index] < float('inf'):
# 存放弧尾下标
Path.append(Vertex)
else:
Path.append(-1)
index += 1
# 以顶点Vertex为源点
Dist[Vertex] = 0
Path[Vertex] = 0
flag[Vertex] = True
index = 1
while index < self.vexnum:
minDist = float('inf')
# 寻找源点到下一个顶点wVertex的最短路径
for i in range(self.vexnum):
if not flag[i] and Dist[i] < minDist:
wVertex = i
minDist = Dist[i]
flag[wVertex] = True
sVertex = 0
minDist = float('inf')
# 更新源点到终点sVertex的最短路径
while sVertex < self.vexnum:
if not flag[sVertex]:
if self.arcs[wVertex][sVertex] < minDist and \
Dist[wVertex] + self.arcs[wVertex][sVertex] < Dist[sVertex]:
# 距离更新
Dist[sVertex] = Dist[wVertex] + self.arcs[wVertex][sVertex]
Path[sVertex] = wVertex
sVertex += 1
index += 1
# 输出信息
self.ShortestPathDijkstra(Vertex, Dist, Path)
def ShortestPathDijkstra(self, Vertex, Dist, Path):
"""
输出从顶点Vertex到其余顶点的最短路径
:param Vertex:
:param Dist:
:param Path:
:return:
"""
tPath = []
index = 0
while index < self.vexnum:
# index是路径终点
if index != Vertex:
print('顶点' + self.vertexs[Vertex].data + '到达顶点' + self.vertexs[index].data + '的路径及长度为:')
# 从源点Vertex到终点index中间有可能经过了多个顶点
tPath.append(index)
former = Path[index]
while former != Vertex:
tPath.append(former)
former = Path[former]
tPath.append(Vertex)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[index])
index += 1
4. Floyd算法
F
l
o
y
d
Floyd
Floyd算法 ，中文名叫弗洛伊德算法，它常用于求解求解每一对顶点之间的最短路径 。
假设
G
=
{
V
,
{
A
}
}
G=\{V, \{A\}\}
G={V,{A}}是含有
n
n
n个顶点的有向网，使用
F
l
o
y
d
Floyd
Floyd算法求图中每一对顶点间的最短路径的基本思路如下：
(1) 对于图
G
G
G中任意两个顶点
v
v
v和
w
w
w ，将顶点
v
v
v和顶点
w
w
w的最短路径的长度记为
D
v
w
D_{vw}
Dvw ，并依次判断其余各顶点是否为这两个顶点间最短路径上的顶点。对于除了顶点
v
v
v和顶点顶点
w
w
w的任意顶点
u
u
u，将顶点
v
v
v和顶点
u
u
u的最短路径的长度记为
D
v
u
D_{vu}
Dvu ，并顶点
u
u
u和顶点
w
w
w的最短路径的长度记为
D
u
w
D_{uw}
Duw ，若
D
v
u
+
D
u
w
<
D
v
w
D_{vu}+D_{uw}<D_{vw}
Dvu+Duw<Dvw，则将
D
v
w
D_{vw}
Dvw的值修改为
D
v
u
+
D
u
w
D_{vu}+D_{uw}
Dvu+Duw ，即顶点
v
v
v和顶点
w
w
w的最短路径经过顶点
u
u
u；
(2) 重复上述过程 ，直至图中每一顶点间的最短路径都被求出 。
当然了，也可以对每个顶点使用
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法来求得每对顶点的最短路径 。对于
F
l
o
y
d
Floyd
Floyd算法 ，这里使用一个辅助二维数组Dist ，用来存储源点到每一对顶点间的最短路径长度，二维数组Path来存储每一条最短路径中倒数第二个顶点的下标(弧尾下标)。下面结合着
F
l
o
y
d
Floyd
Floyd算法来分析一下最上面的那个有向网（由于顶点对较多 ，这里选择
A
−
I
A-I
A−I的最短路径进行说明）：
F
l
o
y
d
Floyd
Floyd算法代码实现如下：
def Floyd(self):
"""
Floyd算法, 计算每一对顶点间的最短距离
:return:
"""
Dist = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
Path = [[0 for _ in range(self.vexnum)] for _ in range(self.vexnum)]
for row in range(self.vexnum):
for column in range(self.vexnum):
Dist[row][column] = self.arcs[row][column]
if self.arcs[row][column] < float('inf') and row != column:
Path[row][column] = row
else:
Path[row][column] = -1
# 判断图中任意两个顶点的最短路径是否经过了结点uVertex
for uVertex in range(self.vexnum):
for vVertex in range(self.vexnum):
for wVertex in range(self.vexnum):
if vVertex != wVertex and \
Dist[vVertex][uVertex] + Dist[uVertex][wVertex] < Dist[vVertex][wVertex]:
Dist[vVertex][wVertex] = Dist[vVertex][uVertex] + Dist[uVertex][wVertex]
Path[vVertex][wVertex] = Path[uVertex][wVertex]
# 输出每一组顶点间的最短路径
self.ShortestPathFloyd(Dist, Path)
def ShortestPathFloyd(self, Dist, Path):
"""
输出每一组顶点间的最短路径
:param Dist:
:param Path:
:return:
"""
tPath = []
for start in range(self.vexnum):
for end in range(self.vexnum):
if start != end and Dist[start][end] < float('inf'):
print('从顶点' + self.vertexs[start].data + '到顶点' + self.vertexs[end].data +
'的路径及长度为:')
tVertex = Path[start][end]
tPath.append(end)
while tVertex != -1 and tVertex != start:
tPath.append(tVertex)
tVertex = Path[start][tVertex]
tPath.append(start)
while len(tPath) > 0:
print(self.vertexs[tPath.pop()].data, end='')
print('\t\t%d' % Dist[start][end])
5. 代码测试
测试代码如下：
if __name__ == '__main__':
graph = Graph(kind='Dinetwork')
graph.CreateGraph(vertex_list=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'],
edge_list=[('A', 'B', 4), ('A', 'C', 8), ('B', 'C', 3), ('B', 'D', 8),
('C', 'E', 1), ('C', 'F', 6), ('D', 'G', 7), ('D', 'H', 4),
('E', 'D', 2), ('E', 'F', 6), ('F', 'H', 2), ('G', 'I', 9),
('H', 'G', 14), ('H', 'I', 10)])
print('{:*^30}'.format('Dijkstra算法'))
# 起始位置的index为0
graph.Dijkstra(0)
print('{:*^30}'.format('Floyd算法'))
graph.Floyd()
测试结果如下：
这里只看了一条 ，就是从顶点
A
A
A到顶点
I
I
I的路径，可以看到
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法和
F
l
o
y
d
Floyd
Floyd算法求得的最短路径都是24 。
