• 技术文章 >Python技术 >Python基础教程

    Python Dijkstra算法是什么

    小妮浅浅小妮浅浅2021-09-08 09:15:18原创2996

    说明

    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学习指路:python基础教程

    本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。

    专题推荐:python dijkstra算法
    上一篇:python列表中if语句的用途 下一篇:python最短路径问题的介绍

    相关文章推荐

    • python生成器的三种构建方法• python return和yield有什么不同• python迭代器的取值方法• python迭代器的优缺点• python使用Pyecharts绘制疫情分布图• 如何查看python解释器的路径• python用户输入的方法• python if-elif-else语句是什么• python列表中if语句的用途• Python f-string字符串格式化的介绍

    全部评论我要评论

    © 2021 Python学习网 苏ICP备2021003149号-1

  • 取消发布评论
  • 

    Python学习网