温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python中Dijkstra算法有什么用

发布时间:2021-08-09 13:44:36 来源:亿速云 阅读:163 作者:小新 栏目:编程语言

小编给大家分享一下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算法有什么用”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI