图算法之最短路径

求图中某一个顶点到其他顶点的权值总和最少的路径,这类问题就称为最短路径问题。

Dijkstra算法

迪杰斯特拉(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)
0%