Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
程序员文章站
2022-04-16 10:00:54
本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法)。分享给大家供大家参考,具体如下:
# coding:utf-8
# Dijkst...
本文实例讲述了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数据结构与算法之图的广度优先与深度优先搜索算法示例
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
Python数据结构与算法之图的基本实现及迭代器实例详解
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
图的数据结构及深度优先、广度优先、最短路径算法python实现
-
Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例
-
Python数据结构与算法之图的基本实现及迭代器实例详解
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
python基础编程:Python数据结构与算法之图的广度优先与深度优先搜索算法示例