Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
作者:hanahimi 时间:2023-03-16 21:02:45
本文实例讲述了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程序设计有所帮助。
来源:https://www.cnblogs.com/hanahimi/p/4692638.html
标签:Python,数据结构,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
numpy中实现二维数组按照某列、某行排序的方法
2022-07-16 00:18:03
详解 PyTorch Lightning模型部署到生产服务中
2021-10-23 01:17:25
![](https://img.aspxhome.com/file/2023/6/90416_0s.jpg)
设计与表达
2009-07-27 11:45:00
![](https://img.aspxhome.com/file/UploadPic/20097/27/0907_sheji_biaoda_01-84s.jpg)
40行Python代码实现天气预报和每日鸡汤推送功能
2022-05-14 00:38:41
![](https://img.aspxhome.com/file/2023/6/125166_0s.jpg)
Python中利用sqrt()方法进行平方根计算的教程
2022-09-17 13:11:25
深入理解JS中attribute和property的区别
2024-04-10 16:19:32
![](https://img.aspxhome.com/file/2023/6/136706_0s.png)
pycharm中venv文件夹自定义处理方式图解
2022-06-28 22:46:53
![](https://img.aspxhome.com/file/2023/8/132438_0s.png)
python导入pandas具体步骤方法
2022-08-14 16:01:03
Python实现获取系统临时目录及临时文件的方法示例
2022-03-11 00:42:04
golang的强制类型转换实现
2024-01-31 03:29:38
Python面向对象程序设计类的多态用法详解
2021-05-28 20:21:29
three.js中文文档学习之创建场景
2023-08-22 21:02:00
JavaScript中的全局对象介绍
2024-04-22 22:41:29
用python生成mysql数据库结构文档
2021-05-15 12:04:33
![](https://img.aspxhome.com/file/2023/5/67945_0s.png)
python列表中remove()函数的使用方法详解
2021-05-13 22:52:46
![](https://img.aspxhome.com/file/2023/8/94058_0s.png)
NumPy 基本切片和索引的具体使用方法
2023-02-11 20:47:50
mysql 8.0.16 压缩包安装配置方法图文教程
2024-01-14 13:06:39
![](https://img.aspxhome.com/file/2023/8/119728_0s.jpg)
windows系统mysql5.7.18安装图文教程
2024-01-26 04:40:59
![](https://img.aspxhome.com/file/2023/1/69141_0s.png)
Mysql一些复杂的sql语句(查询与删除重复的行)
2024-01-22 19:35:01
详解Python调用系统命令的六种方法
2023-11-20 02:22:36
![](https://img.aspxhome.com/file/2023/8/125038_0s.png)