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://blog.csdn.net/littlethunder/article/details/9748519