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

建议先看看前言: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++实现可见:

  • 最短路径算法—Dijkstra(迪杰斯特拉)算法分析与实现(C/C++)
  • 最短路径算法—Bellman最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++)
  •  

    DATE: 2012.1.8 @ Home By Tanky Woo

    发布者

    Tanky Woo

    Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

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

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注