首页 > 搜索 > python最短路算法,Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

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

互联网 2020-10-27 11:15:48
在线算命,八字测算命理

本文实例讲述了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)
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多