189 8069 5689
小编给大家分享一下Python中Dijkstra算法有什么用，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
创新互联建站成立于2013年，是专业互联网技术服务公司，拥有项目网站设计制作、网站设计网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元合川做网站,已为上家服务,为合川各地企业和个人服务,联系电话:13518219792
说明
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算法有什么用”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联行业资讯频道！