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

yipeiwu_com7年前Python基础

本文实例讲述了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("【听图阁-专注于Python设计】测试结果:")
print dis.values()

运行结果:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

相关文章

使用Python中的线程进行网络编程的入门教程

引言 对于 Python 来说,并不缺少并发选项,其标准库中包括了对线程、进程和异步 I/O 的支持。在许多情况下,通过创建诸如异步、线程和子进程之类的高层模块,Python 简化了各种...

Python面向对象之多态原理与用法案例分析

Python面向对象之多态原理与用法案例分析

本文实例讲述了Python面向对象之多态原理与用法。分享给大家供大家参考,具体如下: 目标 多态 面向对象三大特性 封装 根据 职责 将 属性 和 方法 封装 到一个抽象的 类 中 定义...

浅析Python 实现一个自动化翻译和替换的工具

浅析Python 实现一个自动化翻译和替换的工具

一个可能你似曾相识的场景 阅读内容包含大量英文的 PPT、Word、Excel 或者记事本时,由于英语不熟悉,为了流利地阅读,需要打开浏览器进入谷歌翻译的主界面,然后把英文复制到谷歌翻译...

Python实现计算文件夹下.h和.cpp文件的总行数

平时自己写了很多代码,但从没好好计算总共写了多少行,面试时被问起来,就傻了。。。闲来无事,写个python程序来统计下 import os ###################...

解决Pytorch 加载训练好的模型 遇到的error问题

解决Pytorch 加载训练好的模型 遇到的error问题

这是一个非常愚蠢的错误 debug的时候要好好看error信息 提醒自己切记好好对待error!切记!切记! -----------------------分割线------------...