Tanky WooRSS

《算法导论》学习总结 — XX.第24章 单源最短路径

08 Jan 2012
这篇博客是从旧博客 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