问题

最短路径问题的Dijkstra算法

是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

这个算法的python实现途径很多,网上能够发现不少。这里推荐一个我在网上看到的,本来打算自己写,看了这个,决定自己不写了,因为他的已经太好了。

解决(Python)

  1. #!/usr/bin/env python
  2. #coding:utf-8
  3. # Dijkstra's algorithm for shortest paths
  4. # David Eppstein, UC Irvine, 4 April 2002
  5. # code source:http://www.algolist.com/code/python/Dijkstra%27s_algorithm
  6. from priodict import priorityDictionary
  7. defDijkstra(G,start,end=None):
  8. D ={}# dictionary of final distances
  9. P ={}# dictionary of predecessors
  10. Q = priorityDictionary()# est.dist. of non-final vert.
  11. Q[start]=0
  12. for v in Q:
  13. D[v]= Q[v]
  14. if v ==end:break
  15. for w in G[v]:
  16. vwLength = D[v]+ G[v][w]
  17. if w in D:
  18. if vwLength < D[w]:
  19. raiseValueError,"Dijkstra: found better path to already-final vertex"
  20. elif w notin Q or vwLength < Q[w]:
  21. Q[w]= vwLength
  22. P[w]= v
  23. return(D,P)
  24. def shortestPath(G,start,end):
  25. D,P =Dijkstra(G,start,end)
  26. Path=[]
  27. while1:
  28. Path.append(end)
  29. ifend== start:break
  30. end= P[end]
  31. Path.reverse()
  32. returnPath