这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
建议先看看前言:http://www.wutianqi.com/?p=2298
更多单源最短路径算法见我的算法专题:http://www.wutianqi.com/sfzt.html
这里我补充一些里面未写到的。
源 --- “起点”的意思
我总喜欢把单源最短路径和MST的概念弄混,囧~~~
单源最短路径问题:
从给定的源顶点s到每个顶点v的最短路径。
------->变体:
1.单终点最短路径
2.单对顶点最短路径
3.每对顶点间最短路径
定理24.1:
最短路径的子路径是最短路径----->利用反证法来证明
负权值边:
这里要区分负权值边和负权回路,详细见图24-1。
可以有负权值边,但是不能有负权回路。
回路:
最短路径上不会有回路----->利用反证法证明
所以至多有|V|-1条边
松弛技术:
松弛技术(relaxation),是为了缩进上界,即逐步来缩进源点s到顶点v的最短路径上的权值的上界。在Bellman-Ford算法上用到了,详细可见:最短路径算法—Bellman-Ford(贝尔曼-福特)算法分析与实现(C/C++)
Bellman-Ford和Dijkstra:
上面提到了,Bellman-Ford算法用到了松弛技术,它可以处理带有负权值的边,而Dijkstra则只能处理权值为正数的边,不过Dijkstra的运行时间要比Bellman-Ford的低。
两者的具体分析及C/C++实现可见:
DATE: 2012.1.8 @ Home By Tanky Woo