说明
1、Dijkstra算法是数据结构、图论、运筹学等基础教学算法的经典最短路径算法。
有趣的是，Dijkstra算法通常是以贪婪的方式描述的，而Dijkstra算法则被视为运筹学中的动态规划。
2、从起点开始，Dijkstra算法采用贪心法。
每次遍历一个距离起点最近但没有到达的邻接顶点，层层展开，直到结束。
Dijkstra算法求解加权最短路径的最佳解，其时间复杂度为o^2。当边数远小于n^2时，可以降低复杂度，并以堆叠结构的形式将其降低为o^2`(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基础教程
本文教程操作环境：windows7系统Python 3.9.1，DELL G3电脑。