【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