说明
1、Dijkstra算法是经典的最短路径算法,它是数据结构、图论、运筹学等基础教学算法。
令人感兴趣的是,Dijkstra算法通常是按照贪心方法来描述的,而在运筹学中把Dijkstra算法视为动态规划。
2、Dijkstra算法从起始点开始,采用贪心法。
每一遍遍历一个距离起点最近且没有到达的邻接顶点,层层展开,直至结束。
Dijkstra算法求解加权最短路径的最优解,其时间复杂度为O^2。当边数远小于n^2时,复杂度可以降低,并以堆结构的形式将其降低为O`(m+n)log(n))。
Dijkstar算法无法处理负权边,这是由贪心法的选择规则所决定的。
实例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
以上就是Python Dijkstra算法的介绍,希望对大家有所帮助。更多Python学习指路:python基础教程
本文教程操作环境:windows7系统、Python 3.9.1,DELL G3电脑。