最短路径问题的Dijkstra算法
2024-10-22 02:43:48
问题
最短路径问题的Dijkstra算法
是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法终于得到一个最短路径树> 。该算法经常使用于路由算法或者作为其它图算法的一个子模块。
这个算法的python实现途径非常多,网上可以发现不少。这里推荐一个我在网上看到的。本来打算自己写,看了这个,决定自己不写了。由于他的已经太好了。
下面代码来自网络。可是我不能写来源。由于写了来源网址,这里就不让我发出这篇文章。这不是逼着我剽窃吗?
解决(Python)
#!/usr/bin/env python
#coding:utf-8
# Dijkstra's algorithm for shortest paths
# David Eppstein, UC Irvine, 4 April 2002
from priodict import priorityDictionary
def Dijkstra(G,start,end=None):
D = {} # dictionary of final distances
P = {} # dictionary of predecessors
Q = priorityDictionary() # est.dist. of non-final vert.
Q[start] = 0
for v in Q:
D[v] = Q[v]
if v == end: break
for w in G[v]:
vwLength = D[v] + G[v][w]
if w in D:
if vwLength < D[w]:
raise ValueError, "Dijkstra: found better path to already-final vertex"
elif w not in Q or vwLength < Q[w]:
Q[w] = vwLength
P[w] = v
return (D,P)
def shortestPath(G,start,end):
D,P = Dijkstra(G,start,end)
最新文章
- java多线程解读二(内存篇)
- 后台拼接input 后,动态获取input的值
- python 中BeautifulSoup入门
- HTML+AngularJS+Groovy如何实现登录功能
- 【POJ 3294】Life Forms 不小于k个字符串中的最长子串
- shell 调试手段总结
- Qt工程转化为Vs工程
- [转]解决WebClient或HttpWebRequest首次连接缓慢问题
- Horizontal Toolbar With Navigational Buttons Form Sample For Oracle Forms 10g/11g
- hdu 1505(dp求最大子矩阵)
- Linux 系统下原版 texlive 2016 的安装与配置
- 当 tcpdump -w 遇到 Permission denied
- android5.0中RecycleView的用法
- Swift语言指南(七)--语言基础之布尔值和类型别名
- CODE[VS]-求和-整数处理-天梯青铜
- Base64转换二进制文件对象 Blob/Base64转换 File 对象
- ●BZOJ 4826 [Hnoi2017]影魔
- 指令汇B新闻客户端开发(四) 自动轮播条
- vim/network/ssh语法
- CSS实现移动端横向滑动