导语：
本文主要介绍了关于Python Dijkstra算法是什么的相关知识，希望可以帮到处于编程学习途中的小伙伴
说明
1. Dijkstra算法是经典的最短路径算法，是数据结构、图论、运筹学等基础教学算法。
有趣的是，Dijkstra 算法通常用贪心方法来描述，而在运筹学中，Dijkstra 算法被认为是动态规划。
2、Dijkstra算法从起始点开始，采用贪心法。
每一次pass都会遍历一个离起点最近但还没有到达的相邻顶点，逐层展开直到结束。
Dijkstra算法求解加权最短路径的最优解，其时间复杂度为O^2。当边数远小于n^2时，可以降低复杂度，以堆结构的形式降低到O`(m+n)log(n))。
Dijkstar 的算法不能处理负权边缘，这是由贪心法的选择规则决定的。
实例
def dijstra(adj, src, dst, n):
dist = [Inf] * n
dist[src] = 0
book = [0] * n # 记录已经确定的顶点
# 每次找到起点到该点的最短途径
u = src
for _ in range(n-1): # 找n-1次
book[u] = 1 # 已经确定
# 更新距离并记录最小距离的结点
next_u, minVal = None, float('inf')
for v in range(n): # w
w = adj[u][v]
if w == Inf: # 结点u和v之间没有边
continue
if not book[v] and dist[u] + w < dist[v]: # 判断结点是否已经确定了，
dist[v] = dist[u] + w
if dist[v] < minVal:
next_u, minVal = v, dist[v]
# 开始下一轮遍历
u = next_u
print(dist)
return dist[dst]
本文教程操作环境：windows7系统、Python 3.9.1，DELL G3电脑。
本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！
内容反馈