首页 > 代码库 > 最短路径问题的Dijkstra算法
最短路径问题的Dijkstra算法
问题
最短路径问题的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)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。