图算法之最短路径

最短路径问题是图论中非常经典的问题之一,旨在寻找图中两顶点之间的最短路径。作为一个基本工具,实际应用中的许多优化问题,如管道铺设、线路安排等,都可被归纳为最短路径问题来解决。

Dijkstra算法

寻求从一固定起点到其余各点的最短路径,最有效的算法之一是E.W.Dijkstra于1959年提出的Dijkstra算法。该算法主要是针对没有负值的有向图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def dijkstra(nodes, graph, start, goal):
'''
求解两顶点间最短路径
'''
if start == goal:
return [start]

n = len(nodes)
explored = set(start) # 记录已探索过的顶点
quene = [[start]]
while quene:
path = quene.pop(0)
curnode = nodes.index(path[-1])
for i, w in enumerate(graph[curnode]):
if w < 9999:
nextnode = nodes[i]
if nextnode not in explored:
explored.add(nextnode)
path2 = path + [nextnode]
if nextnode == goal:
return path2
else:
quene.append(path2)

return []

if __name__ == '__main__':
nodes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

MAX = 9999
matrix = [[MAX, 10, MAX, MAX, MAX, 11, MAX, MAX, MAX],
[10, MAX, 18, MAX, MAX, MAX, 16, MAX, 12],
[MAX, 18, MAX, 22, MAX, MAX, MAX, MAX, 8],
[MAX, MAX, 22, MAX, 20, MAX, MAX, 16, 21],
[MAX, MAX, MAX, 20, MAX, 26, 7, 19, MAX],
[11, MAX, MAX, MAX, 26, MAX, 17, MAX, MAX],
[MAX, 16, MAX, MAX, 7, 17, MAX, 19, MAX],
[MAX, MAX, MAX, 16, 19, MAX, 19, MAX, MAX],
[MAX, 12, 8, 21, MAX, MAX, MAX, MAX, MAX]]

res = dijkstra(nodes, matrix, 'a', 'g')
print(res)

Floyd算法

利用Dijkstra算法,当然还可以寻求赋权图中所有顶点对之间的最短路径。具体方法是:每次以不同的顶点作为起点,例用Dijkstra算法求出该起点到其余顶点之间的最短路径,反复执行n-1(n为顶点个数)次这样的操作,就可以得到每对顶点之间的最短路径。但这样做需要大量的重复计算,效率不高。为此,R.W.Floyd另辟蹊径,于1962年提出了一个直接求任意两顶点间最短路径的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

if __name__ == '__main__':
MAX = 9999
matrix = [[MAX, 10, MAX, MAX, MAX, 11, MAX, MAX, MAX],
[10, MAX, 18, MAX, MAX, MAX, 16, MAX, 12],
[MAX, 18, MAX, 22, MAX, MAX, MAX, MAX, 8],
[MAX, MAX, 22, MAX, 20, MAX, MAX, 16, 21],
[MAX, MAX, MAX, 20, MAX, 26, 7, 19, MAX],
[11, MAX, MAX, MAX, 26, MAX, 17, MAX, MAX],
[MAX, 16, MAX, MAX, 7, 17, MAX, 19, MAX],
[MAX, MAX, MAX, 16, 19, MAX, 19, MAX, MAX],
[MAX, 12, 8, 21, MAX, MAX, MAX, MAX, MAX]]

dis, path = floyd(matrix)
print('所有顶点对之间的最短路径为:\n', np.matrix(dis))
print('路由矩阵为:\n', path)
0%