【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 的求解
• 对于恢复最短路径，策略有何不同? 那种更优?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾