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

18 浏览量更新于2023-03-03 评论收藏 56KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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

例例

本文实例讲述了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数据结构之图深度优先和广度优

先实例详解python深度优先搜索和广度优先搜索python 递归深度优先搜索与广度优先搜索算法模拟实现Python数据结构与算

法之图结构（Graph）实例分析Python算法之图的遍历Python数据结构与算法之图的基本实现及迭代器实例详解python图的深

度优先和广度优先算法实例分析

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余0页未读，立即下载

评论0

weixin_38569166

粉丝: 7
资源: 878

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈