【Python排序搜索基本算法】之Dij
短信预约 -IT技能 免费直播动态提醒
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
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
