Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
发布时间：2020-12-17 07:45:09 所属栏目：Python 来源：网络整理
导读：本篇章节讲解Python数据结构与算法之图的最短路径(Dijkstra算法)。供大家参考研究具体如下： # coding:utf-8# Dijkstra算法――通过边实现松弛# 指定一个点到其他各顶点的路径――单源最短路径# 初始化图参数G = {1:{1:0,2:1,3:12},2:{2:0,3:9,4:3
|
本篇章节讲解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相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》 希望本文所述对大家Python程序设计有所帮助。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
