Python排序搜索基本算法之：Dijkstra's Algorithm

编程 Python 搜索算法

创建时间:2017-11-18 02:58

字数:237 阅读:

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)

按照输出结果用粗线表示最短路径树如下：
[0, 5, 3, 6, 7, 9]
[0, 2, 0, 2, 2, 3]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 jyzh@yahoo.com