Dijkstra算法和前一篇的Prim算法非常像，区别就在于Dijkstra算法向最短路径树（SPT）中添加顶点的时候，是按照ta与源点的距离顺序进行的。OSPF动态路由协议就是用的Dijkstra算法。下面还以那个图的例子为例：
代码如下：
- _=float('inf')
- def dijkstra(graph,n):
- dis=[0]*n
- flag=[False]*n
- pre=[0]*n
- flag[0]=True
- k=0
- for i in range(n):
- dis[i]=graph[k][i]
- for j in range(n-1):
- mini=_
- for i in range(n):
- if dis[i]<mini and not flag[i]:
- mini=dis[i]
- k=i
- if k==0:#不连通
- return
- flag[k]=True
- for i in range(n):
- if dis[i]>dis[k]+graph[k][i]:
- dis[i]=dis[k]+graph[k][i]
- pre[i]=k
- # print(k)
- return dis,pre
- if __name__=='__main__':
- n=6
- graph=[
- [0,6,3,_,_,_],
- [6,0,2,5,_,_],
- [3,2,0,3,4,_],
- [_,5,3,0,2,3],
- [_,_,4,2,0,5],
- [_,_,_,3,5,0],
- ]
- dis,pre=dijkstra(graph,n)
- print(dis)
- print(pre)
输出如下：
- [0, 5, 3, 6, 7, 9]
- [0, 2, 0, 2, 2, 3]
按照输出结果用粗线表示最短路径树如下：
http://tm.pm.netease.com:8175/projects/runner/wiki/Wiki