【Python排序搜索基本算法】之Dij

发布时间：2019-09-21 10:54:33编辑：auto阅读（1891）

            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

关键字：

上一篇： 用Python编写一个简单的Http S

下一篇： Python+Xml +操作+增删改查