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

脚本专栏 2024/11/7 佚名

3 2 1

圆月山庄资源网 Design By www.vgjia.com

本文实例讲述了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程序设计有所帮助。

Python,数据结构,算法,图,最短路径,Dijkstra算法

标签：

Python,数据结构,算法,图,最短路径,Dijkstra算法

圆月山庄资源网 Design By www.vgjia.com

广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com

圆月山庄资源网 Design By www.vgjia.com

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

暂无评论...

P70系列延期，华为新旗舰将在下月发布

3月20日消息，近期博主@数码闲聊站透露，原定三月份发布的华为新旗舰P70系列延期发布，预计4月份上市。

而博主@定焦数码爆料，华为的P70系列在定位上已经超过了Mate60，成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢？
根据目前爆料的消息来看，华为P70系列将推出三个版本，其中P70和P70 Pro采用了三角形的摄像头模组设计，而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智，但辨识度绝对拉满。

更新日志

2024年11月07日

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

Python,数据结构,算法,图,最短路径,Dijkstra算法

Python实现自动发送邮件功能

django站点管理详解

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

P70系列延期，华为新旗舰将在下月发布

更新日志

友情链接