本文实例讲述了Python数据结构与算法之图的最短路径(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
|
# coding:utf-8
# Dijkstra算法——通过边实现松弛
# 指定一个点到其他各顶点的路径——单源最短路径
# 初始化图参数
G = { 1 :{ 1 : 0 , 2 : 1 , 3 : 12 },
2 :{ 2 : 0 , 3 : 9 , 4 : 3 },
3 :{ 3 : 0 , 5 : 5 },
4 :{ 3 : 4 , 4 : 0 , 5 : 13 , 6 : 15 },
5 :{ 5 : 0 , 6 : 4 },
6 :{ 6 : 0 }}
# 每次找到离源点最近的一个顶点,然后以该顶点为重心进行扩展
# 最终的到源点到其余所有点的最短路径
# 一种贪婪算法
def Dijkstra(G,v0,INF = 999 ):
""" 使用 Dijkstra 算法计算指定点 v0 到图 G 中任意点的最短路径的距离
INF 为设定的无限远距离值
此方法不能解决负权值边的图
"""
book = set ()
minv = v0
# 源顶点到其余各顶点的初始路程
dis = dict ((k,INF) for k in G.keys())
dis[v0] = 0
while len (book)< len (G):
book.add(minv) # 确定当期顶点的距离
for w in G[minv]: # 以当前点的中心向外扩散
if dis[minv] + G[minv][w] < dis[w]: # 如果从当前点扩展到某一点的距离小与已知最短距离
dis[w] = dis[minv] + G[minv][w] # 对已知距离进行更新
new = INF # 从剩下的未确定点中选择最小距离点作为新的扩散点
for v in dis.keys():
if v in book: continue
if dis[v] < new:
new = dis[v]
minv = v
return dis
dis = Dijkstra(G,v0 = 1 )
print ( "服务器之家测试结果:" )
print dis.values()
|
运行结果:
希望本文所述对大家Python程序设计有所帮助。
原文链接:https://www.cnblogs.com/hanahimi/p/4692638.html