【7.5】图的最短路径
一、单源最短路径(single-source shortest paths)
给定带权图
G = <V,E>
,其中每条边 (vi,vj) 上的权 W[vi,vj] 是一个 非负实数 。计算从任给的一个源点 s 到所有其他各结点的最短路径
2.1 Dijkstra算法基本思想
-
把所有结点分成两组:
-
第一组 U 包括已确定最短路径的结点
-
第二组 V–U 包括尚未确 定最短路径的结
-
按最短路径长度递增的 顺序逐个把第二组的结 点加到第一组中
-
直至从 s 出发可达结点 都包括进第一组中
Dijkstra单源最短路径迭代过程
Dijkstra单源最短路径算法
Dijkstra算法时间代价分析:
-
每次改变D[i].length
-
不删除,添加一个新值(更小的),作为堆中 新元素。旧值被找到时,该结点一定被标记 为VISITED,从而被忽略
-
在最差情况下,它将使堆中元素数目由 Θ(|V|)增加到Θ(|E|),总的时间代价 Θ((|V|+|E|) log|E|)
Dijkstra算法:
Dijkstra算法不支持负权值:
如果存在总权值为负的回路,则将出现权 值为 -∞ 的情况
如果不存在负权回路呢?Dijkstra算法不受负权边的影响吗?
- 即使不存在负的回路,也可能有在后面出现的负权值, 从而导致整体计算错误
- 主要原因是 Dijkstra 算法是贪心法,当作最小取进来 后,不会返回去重新计算
持负权值的最短路径算法:
- Bellman-Ford 算法
- 参考书 MIT “Introduction to Algorithms”
- SPFA 算法
二、每对结点间的最短路径
- 还能用 Dijkstra 算法吗?
- 以每个结点为起点,调用 n 次 Dijkstra 算法
2.1 Floyd算法求每对结点之间的最短路径
- 用相邻矩阵 adj 来表示带权有向图
- 基本思想:
- 初始化 adj(0) 为相邻矩阵 adj
- 在矩阵 adj(0)上做 n 次迭代,递归地产生一个矩 阵序列adj(1),…,adj(k),…,adj(n)
- 其中经过第k次迭代,adj(k)[i,j] 的值等于从结点 vi 到结点 vj 路径上所经过的结点序号不大于 k 的 最短路径长度
- 动态规划法
最短路径组合情况分析:
由于第 k 次迭代时已求得矩阵 adj(k-1),那么从结点 vi 到 vj 中间结点的序号不大于 k 的最短路径有两种情况:
- 一种是中间不经过结点 vk,那么此时就有 adj(k) [i,j] = adj(k-1)[i,j]
- 另中间经过结点 vk,此时 adj(k) [i,j] < adj(k-1)[i,j], 那么这条由结点 vi 经过 vk 到结点 vj 的中间结点序号不 大于k的最短路径由两段组成
$$adj^{(k)} [i,j] = adj^{(k-1)}[i,k] + adj^{(k-1)}[k,j]$$
每对结点之间最短路径的Floyd算法
Floyd算法的时间复杂度:
- 三重for循环
- 复杂度是Θ(n^3)
讨论:Dijkstra 找最小 Dist 值:
- 如果不采用最小堆,而采用每次遍历的 方式寻找最小值,与用最小堆实现的 Dijkstra 相比,时间效率如何?
讨论:Floyd算法保持 pre 的方式:
将“D[i][j].pre= D[v][j].pre” 改为 “ D[i][j].pre = v” 是否可以?
- 上述两种方案不影响 D[i][j].length 的求解
- 对于恢复最短路径,策略有何不同? 那种更优?
参考资料
北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾
这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn