Python培训之Dijkstra算法是什么

　　Python Dijkstra算法是什么

　　说明

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

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

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

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

　　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]

　　以上就是Python Dijkstra算法的介绍，希望对大家有所帮助。更多Python学习指路：请关注多测师。https://www.e70w.com/xwzx/