python

超轻量级php框架startmvc

Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

更新时间:2020-05-14 10:06:01 作者:startmvc
本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考

本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考,具体如下:


# 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 数据结构 算法 最短路径 Dijkstra算法