首页 > 正在进行安全检测...

正在进行安全检测...

发布时间：2024-01-11 16:38:17 来源：文档文库

小中大

字号：

手机查看

彻底弄懂最短路径问题
只想说：温故而知新，可以为师矣。我大二的《数据结构》是由申老师讲的，那时候不怎么明白，估计太理论化了(ps：或许是因为我睡觉了；今天把老王的2011年课件又看了一遍，给大二的孩子们又讲了一遍，随手谷歌了N多资料，算是彻底搞懂了最短路径问题。请读者尽情享用……
我坚信：没有不好的学生，只有垃圾的教育。不过没有人理所当然的对你好，所以要学会感恩。
一.问题引入
问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。笔者认为任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。
二.Dijkstra算法
该算法在《数据结构》课本里是以贪心的形式讲解的，不过在《运筹学》教材里被编排在动态规划章节，建议读者两篇都看看。

观察右边表格发现除最后一个节点外其他均已经求出最短路径。
(1迪杰斯特拉(Dijkstra算法按路径长度(看下面表格的最后一行，就是next点递增次序产生最短路径。先把V分成两组：
•S：已求出最短路径的顶点的集合
•V-S=T：尚未确定最短路径的顶点集合
将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦）。
(2求最短路径步骤
1.初使时令S={V0},T={其余顶点}，T中顶点对应的距离值，若存在，为弧上的权值（和ＳＰＦＡ初始化方式不同），若不存在，为Inf。

本文来源：https://www.2haoxitong.net/k/doc/904e26f4af1ffc4fff47ac10.html