最短路径问题（2）————Dijkstra算法（迪杰斯特拉）

作者： 作者的头像   Meng123456 ,  2022-02-09 18:49:46 ,  所有人可见 ,  阅读 576

3


1

BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图，Dijkstra算法适用于有权图和无权图

带权路径⻓度——当图是带权图时，⼀条路径上所有边的权值之和，称为该路径的带权路径⻓度

算法解析

初始
1.png

第一轮
2·1.png
2·2.png
2·3.png
2·4.png
2·5.png
2·6.png

第二轮
3·1.png
3·2.png
3·3.png
3·4.png
3·5.png

第三轮
4·1.png
4·2.png
4·3.png
4·4.png
4·5.png
4·6.png

第四轮
5·1.png
5·2.png
5·3.png
5·4.png

使⽤数组信息
6.png

复杂度分析
7.png

不适用于负权值带权图
8·1.png
8·2.png
8·3.png

对⽐：Prim 算法的实现思想
9·1.png

0 评论