【Algorithms 4】算法（第4版）学习笔记 18 - 4.4 最短路径

前言

本篇主要内容包括：APIs、最短路径性质、Dijkstra 算法 、无环加权有向图 以及 负权重。

参考目录

• B站 普林斯顿大学《Algorithms》视频课
  （请自行搜索。主要以该视频课顺序来进行笔记整理，课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。）
• 微信读书《算法（第4版）》
  （本文主要内容来自《4.4 最短路径》）
• 官方网站
  （有书本配套的内容以及代码）

学习笔记

注1：下面引用内容如无注明出处，均是书中摘录。
注2：所有 demo 演示均为视频 PPT demo 截图。
注3：如果 PPT 截图中没有翻译，会在下面进行汉化翻译，因为内容比较多，本文不再一一说明。

0：引入介绍

加权有向图的最短路径（shortest paths in an edge-weighted digraph）：

最短路径的应用：

![L15-44ShortestPaths_03]

• PERT/CPM：计划评审技术/关键路径法
• 地图路线规划
• 接缝雕刻（图像缩放中的内容感知算法）
• 纹理映射（计算机图形学中将图像纹理贴到三维模型表面的技术）
• 机器人导航技术
• TeX 中的排版设置
• 城市交通规划
• VLSI 芯片的最佳流水线设计
• 电话营销员操作员调度问题
• 电信消息的路由选择
• 网络路由协议（如 OSPF、BGP、RIP）
• 利用货币兑换市场中的套利机会
• 根据既定交通拥堵模式确定卡车最优行驶路线

Shortest path is a really interesting and important problem solving model. There’s all kinds of important practical problems that can be recast as shortest paths problems. And because we have efficient solutions to the shortest path, efficient algorithms for finding shortest paths, we have efficient solutions to all these kinds of problems.

最短路径是一个非常有趣且重要的问题解决模型。许多重要的实际问题都可以被重新表述为最短路径问题。正因为如此，我们拥有寻找最短路径的有效解决方案，即高效的最短路径算法，因此也就拥有了解决这类各种问题的有效方法。

最短路径的不同类型：

顶点类型：

• 单源：从一个顶点 s 到其他所有顶点。
• 单汇点：从每个顶点到另一个特定顶点 t。
• 源汇点：从一个顶点 s 到另一个顶点 t。
• 全对全：在所有顶点对之间。

边权重限制：

• 非负权重：所有边的权重都是非负数。
• 欧几里得权重：边权重基于欧几里得距离。
• 任意权重：边的权重可以是任意数值。

循环条件：

• 无有向循环：图中不存在有向循环。
• 无负权循环：图中不存在权重总和为负值的循环。

简化假设： 从顶点 s 到每个顶点 v 都存在最短路径。

1：APIs

1.1：API：加权有向边

1.2：Java 实现：加权有向边

edu.princeton.cs.algs4.DirectedEdge

1.3：API：加权有向图

1.4：Java 实现：加权有向图

edu.princeton.cs.algs4.EdgeWeightedDigraph

1.5：API：最短路径

2：最短路径性质

2.1：最短路径的数据结构

目标： 找到从顶点 s 到其他所有顶点的最短路径。

观察结论： 存在一种最短路径树（Shortest Paths Tree, SPT）解法。为什么？

结果： 可以通过两个以顶点索引为键的数组来表示 SPT：

• distTo[v] 表示从顶点 s 到顶点 v 的最短路径长度。
• edgeTo[v] 表示从顶点 s 到顶点 v 的最短路径上的最后一段边。

对应书本的介绍：

2.2：边的松弛 edge relaxation

对边 e = v → w 进行松弛操作时：

• distTo[v] 保存已知从源点 s 到顶点 v 的最短路径长度。
• distTo[w] 保存已知从源点 s 到顶点 w 的最短路径长度。
• edgeTo[w] 记录已知从源点 s 到顶点 w 的最短路径上最后经过的边。
• 若通过边 e = v → w 能够到达顶点 w，并且这条路径比之前已知的从 s 到 w 的最短路径更短，则更新 distTo[w] 以及 edgeTo[w]。

2.3：最优性条件 optimality conditions

命题： 设G是一个带权有向图（edge-weighted digraph），则 distTo[] 数组存储的是从源点 s 到各顶点的最短路径距离，当且仅当满足以下条件：

• distTo[s] = 0，即源点s到自身的最短路径距离为0。
• 对于每个顶点 v，distTo[v] 表示从源点 s 到顶点 v 的某条路径的长度。
• 对于每条边 e = v → w，distTo[w] 的值小于等于从源点 s 经由顶点 v 再到顶点 w 的路径长度，即 distTo[w] ≤ distTo[v] + e.weight()，其中 e.weight() 表示边 v → w 的权重。

对应书本命题 P：

必要性证明：

对应书本的证明：

充分性证明：

对应书本的证明：

2.4：通用算法 generic shortest-paths algorithm

对应书本命题 Q：

3：Dijkstra 算法

3.1：demo 演示

• 按照离源点 s 的距离递增顺序考虑顶点（选取具有最低 distTo[] 值的非树顶点）。
• 将该顶点添加至树结构中，并对其指向的所有边执行松弛操作。

初始状态：

距离 s 最近是顶点 0，从顶点 0 开始：

对从顶点 0 开始的边进行松弛操作：

顶点 0 到 1 为最短路径，继续选择顶点 1：

对从顶点 1 开始的边进行松弛操作：

顶点 0 到 7 为最短路径，继续选择顶点 7：

对从顶点 7 开始的边进行松弛操作：

顶点 0 到 4 为最短路径，继续选择顶点 4：

对从顶点 4 开始的边进行松弛操作：

顶点 4 到 5 为最短路径，继续选择顶点 5：

对从顶点 5 开始的边进行松弛操作：

顶点 5 到 2 为最短路径，继续选择顶点 2：

对从顶点 2 开始的边进行松弛操作：

顶点 2 到 3 为最短路径，继续选择顶点 3：

对从顶点 3 开始的边进行松弛操作：

顶点 2 到 6 为最短路径，继续选择顶点 6：

对从顶点 6 开始的边进行松弛操作：

s 开始的最短路径树：

3.2：证明

对应书本命题 R：

3.3：Java 实现

edu.princeton.cs.algs4.DijkstraSP

edu.princeton.cs.algs4.DijkstraSP#relax

3.4：计算图生成树

Dijkstra 算法应该相当熟悉吧？

• Prim 算法在本质上是相同的算法。
• 两者都属于计算生成树的一类算法。

主要区别在于 选择下一个加入树中的顶点时所依据的规则：

• Prim 算法选择的是距离当前生成树最近的顶点（通过无向边）；
• 而 Dijkstra 算法选择的是距离源点最近的顶点（通过有向路径）。

注： 深度优先搜索（DFS）和广度优先搜索（BFS）也属于这一类用于生成树或遍历图的算法。

3.5：运行时间

（同 Prim 算法）

核心要点：

• 采用数组实现对稠密图（Dense graphs）而言是最佳方案。
• 对于稀疏图（Sparse graphs），二叉堆在性能上要快得多。
• 在对性能要求极高的情况下，使用四路堆（4-way heap）是值得投入精力提升性能的。
• 斐波那契堆在理论上的优越性虽高，但在实际开发中却未必值得进行具体实现。

4：无环加权有向图 edge-weighted DAGs

4.1：demo 演示

• 按拓扑排序考虑顶点。
• 从该顶点出发对所有指向的边进行松弛操作。

初始状态：

首先对顶点进行拓扑排序：

从顶点 0 开始，对从顶点 0 开始的边进行松弛操作：

继续选择顶点 1，并进行松弛操作：

继续选择顶点 4，并进行松弛操作：

继续选择顶点 7，并进行松弛操作：

继续选择顶点 5，并进行松弛操作：

继续选择顶点 2，并进行松弛操作：

继续选择顶点 3，并进行松弛操作：

继续选择顶点 6，并进行松弛操作：

s 开始的最短路径树：

4.2：证明

对应书本命题 S：

4.3：Java 实现

edu.princeton.cs.algs4.AcyclicSP

4.4：最长路径

带权重有向无环图（DAG）中的最短路径问题：

• 对所有边的权重取反。
• 找出这些取反权重后的最短路径。
• 在得到的结果中再次对边的权重取反。

(等价于：在 relax() 函数中反转相等性判断的方向)

关键点： 拓扑排序算法即使在存在负权边的情况下也能正常工作。

5：负权重 negative weights

5.1：失败尝试

Dijkstra 算法： 该算法无法处理具有负权重的边。
重赋权重法： 对所有边权重增加一个常数值的方法无效。
结论： 我们需要采用一种不同的算法来解决此问题。

5.2：负权重环 negative cycles

对应书本定义以及命题 W：

5.3：Bellman-Ford 算法

对应书本命题 X：

5.3.1：demo 演示

重复 V 次：松弛有向图 E 所有边。

初始状态：

初始化，将到源的距离设置为 0：

对顶点 0 所有有向边进行松弛操作：

对顶点 1 所有有向边进行松弛操作：

对顶点 2 所有有向边进行松弛操作：

对顶点 3 所有有向边进行松弛操作：

对顶点 4 所有有向边进行松弛操作：

对顶点 5 所有有向边进行松弛操作：

对顶点 7 所有有向边进行松弛操作：

以上完成第一轮操作。

再次进行松弛操作。

大部分操作与第一轮类似，但也有可以更新的部分：

同理进行后续的循环：

没有更加优化的路径，完成所有松弛操作。

最终得到 s 开始的最短路径树：

5.3.2：算法分析

对应书本命题 Y：

5.4：成本开销小结

• 注释1： 存在有向循环会使问题求解难度增大。
• 注释2： 负权重边的存在会使问题变得更加复杂。
• 注释3： 负权重环会导致问题无法有效解决或无解状态。

6：小结

非负权重：

• 在许多应用中出现。
• Dijkstra 算法的时间复杂度接近线性时间。

无环带权有向图：

• 在某些应用中出现。
• 通过拓扑排序算法可以在线性时间内求解。
• 边的权重可以为负。

负权重和负权重环：

• 在某些应用中出现。
• 如果不存在负权重环，可以通过 Bellman-Ford 算法找到最短路径。
• 若存在负权重环，仍可通过 Bellman-Ford 算法找到一条路径（但可能不是最短路径）。

最短路径问题是广泛应用于问题求解的一个模型。

（完）