Python Dijkstra算法是什么

说明

1、Dijkstra算法是经典的最短路径算法，它是数据结构、图论、运筹学等基础教学算法。

令人感兴趣的是，Dijkstra算法通常是按照贪心方法来描述的，而在运筹学中把Dijkstra算法视为动态规划。

2、Dijkstra算法从起始点开始，采用贪心法。

每一遍遍历一个距离起点最近且没有到达的邻接顶点，层层展开，直至结束。

Dijkstra算法求解加权最短路径的最优解，其时间复杂度为O^2。当边数远小于n^2时，复杂度可以降低，并以堆结构的形式将其降低为O`(m+n)log(n))。

Dijkstar算法无法处理负权边，这是由贪心法的选择规则所决定的。

实例

defdijstra(adj,src,dst,n):
dist=[Inf]*n
dist[src]=0
book=[0]*n#记录已经确定的顶点
#每次找到起点到该点的最短途径
u=src
for_inrange(n-1):#找n-1次
book[u]=1#已经确定
#更新距离并记录最小距离的结点
next_u,minVal=None,float('inf')
forvinrange(n):#w
w=adj[u][v]
ifw==Inf:#结点u和v之间没有边
continue
ifnotbook[v]anddist[u]+w<dist[v]:#判断结点是否已经确定了，
dist[v]=dist[u]+w
ifdist[v]<minVal:
next_u,minVal=v,dist[v]
#开始下一轮遍历
u=next_u
print(dist)
returndist[dst]

以上就是Python Dijkstra算法的介绍，希望对大家有所帮助。更多Python学习指路：Python基础教程