5. 最短路径问题¶
5.1. 最短路径问题¶
在路线图上，连接两个城镇的道路通常标注其距离。 我们可以将道路网络建模为有向图， 其中边用实数标记。 这些数字表示两个顶点之间的距离 （或其他代价度量，如行程时间）。 这些标签根据应用可以称为 权值、 代价 或 距离。 给定这样一个图，一个典型问题是 找到两个指定顶点之间最短路径的总长度。 这不是一个简单的问题，因为最短路径可能不在 连接两个顶点的边上， 而是可能经过一个或多个中间顶点。
待处理
- type: Slideshow
将以下段落与下方的图一起整合到幻灯片中。
例如，在图 19.5.1 中， 从 \(A\) 经 \(B\) 到 \(D\) 的路径代价为 15。 从 \(A\) 直接到 \(D\) 的边代价为 20。 从 \(A\) 经 \(C\)、\(B\) 到 \(D\) 的 路径代价为 10。 因此，从 \(A\) 到 \(D\) 的最短路径为 10 （而不是沿连接 \(A\) 到 \(D\) 的边）。 我们使用符号 \(\mathbf{d}(A, D) = 10\) 表示 从 \(A\) 到 \(D\) 的最短距离为 10。 在图 19.5.1 中， 从 \(E\) 到 \(B\) 没有路径， 所以我们设置 \(\mathbf{d}(E, B) = \infty\)。 我们定义 \(\mathbf{w}(A, D) = 20\) 为边 \((A, D)\) 的权值， 即从 \(A\) 到 \(D\) 的直接连接的权值。 因为从 \(E\) 到 \(B\) 没有边， \(\mathbf{w}(E, B) = \infty\)。 注意 \(\mathbf{w}(D, A) = \infty\)， 因为图 19.5.1 是有向的。 我们假设所有权值为正。
5.1.1. 单源最短路径¶
我们现在将介绍解决 单源最短路径问题 的算法。 给定图 \(\mathbf{G}\) 中的顶点 \(S\)， 找到从 \(S\) 到 \(\mathbf{G}\) 中 每个其他顶点的最短路径。 我们可能只需要两个顶点 \(S\) 和 \(T\) 之间的最短路径。 然而在最坏情况下，找到从 \(S\) 到 \(T\) 的最短路径 要求我们找到从 \(S\) 到每个其他顶点的最短路径。 因此，在最坏情况下， 找到到单个顶点的最短路径的算法 与找到到所有顶点的最短路径一样好。 这里描述的算法只计算到每个顶点的距离， 而不是记录实际路径。 记录路径只需要对算法进行简单的修改。
计算机网络提供了单源最短路径问题的应用。 目标是找到一种最便宜的方式， 让一台计算机向网络上的所有其他计算机广播消息。 网络可以用图来建模， 边权值表示向邻居计算机发送消息的时间或代价。
对于无权图（或所有边具有相同代价的情况）， 可以使用简单的广度优先搜索 找到单源最短路径。 添加权值后，BFS 将不会给出正确答案。
待处理
- type: Slideshow
提供一个幻灯片来演示以下示例。
当边具有不同权值时， 解决此问题的一种方法是按固定顺序处理顶点。 将顶点标记为 \(v_0\) 到 \(v_{n-1}\)， 其中 \(S = v_0\)。 处理顶点 \(v_1\) 时，我们取连接 \(v_0\) 和 \(v_1\) 的边。 处理 \(v_2\) 时，我们考虑从 \(v_0\) 到 \(v_2\) 的 最短距离，并将其与从 \(v_0\) 经 \(v_1\) 到 \(v_2\) 的最短距离进行比较。 处理顶点 \(v_i\) 时， 我们考虑已处理的顶点 \(v_0\) 到 \(v_{i-1}\) 的最短路径。 不幸的是，到 \(v_i\) 的真正最短路径 可能经过 \(j > i\) 的顶点 \(v_j\)。 此算法不会考虑这样的路径。 然而，如果我们按距离从 \(S\) 的顺序处理顶点， 问题就不会发生。 假设我们已按距离从 \(S\) 到最靠近 \(S\) 的 前 \(i-1\) 个顶点的顺序处理； 称这组顶点为 \(\mathbf{S}\)。 我们现在即将处理第 \(i\) 个最近的顶点； 称它为 \(X\)。
从 \(S\) 到 \(X\) 的最短路径的倒数第二个顶点 必须在 \(S\) 中。因此，
换句话说，从 \(S\) 到 \(X\) 的最短路径是 从 \(S\) 到 \(U\) 的所有路径的最小值， 然后从 \(U\) 到 \(X\) 有一条边， 其中 \(U\) 是 \(\mathbf{S}\) 中的某个顶点。
此解法通常被称为 Dijkstra 算法。它通过维护 \(\mathbf{V}\) 中所有顶点 \(X\) 的距离估计值 \(\mathbf{D}(X)\) 来工作。 \(\mathbf{D}\) 的元素被初始化为值 INFINITE 。顶点按照与 \(S\) 的距离顺序进行处理。每当处理一个顶点 \(v\) 时，都会为 \(V\) 的每个邻居 \(X\) 更新 \(\mathbf{D}(X)\) 。以下是 Dijkstra 算法的一个实现。最后，数组 D 将包含最短距离值。
// Compute shortest path distances from s, store them in D
static void Dijkstra(Graph G, int s, int[] D) {
for (int i=0; i<G.nodeCount(); i++) { // Initialize
D[i] = INFINITY;
}
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // Process the vertices
int v = minVertex(G, D); // Find next-closest vertex
G.setValue(v, VISITED);
if (D[v] == INFINITY) { return; } // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w))) {
D[w] = D[v] + G.weight(v, w);
}
}
}
}
// Compute shortest path distances from s, store them in D
static void Dijkstra(Graph G, int s, int[] D) {
for (int i=0; i<G.nodeCount(); i++) { // Initialize
D[i] = INFINITY;
}
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // Process the vertices
int v = minVertex(G, D); // Find next-closest vertex
G.setValue(v, VISITED);
if (D[v] == INFINITY) { return; } // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w))) {
D[w] = D[v] + G.weight(v, w);
}
}
}
}
待处理
- type: AV
提供一个在随机图上运行的 AV。初始版本位于
AV/Development/TopSort/dijkstraAV.*。
在每次遍历主 for 循环时找到
具有最小距离值的未访问顶点这一关键问题
有两个合理的解决方案。
第一种方法是简单地遍历
\(|\mathbf{V}|\) 个顶点的列表以搜索最小值，如下所示：
// Find the unvisited vertex with the smallest distance
static int minVertex(Graph G, int[] D) {
int v = 0; // Initialize v to any unvisited vertex;
for (int i=0; i<G.nodeCount(); i++) {
if (G.getValue(i) != VISITED) { v = i; break; }
}
for (int i=0; i<G.nodeCount(); i++) { // Now find smallest value
if ((G.getValue(i) != VISITED) && (D[i] < D[v])) {
v = i;
}
}
return v;
}
// Find the unvisited vertex with the smallest distance
static int minVertex(Graph G, int[] D) {
int v = 0; // Initialize v to any unvisited vertex;
for (int i=0; i<G.nodeCount(); i++) {
if (G.getValue(i) != VISITED) { v = i; break; }
}
for (int i=0; i<G.nodeCount(); i++) { // Now find smallest value
if ((G.getValue(i) != VISITED) && (D[i] < D[v])) {
v = i;
}
}
return v;
}
待处理
- type: Code
为什么代码要先查找未访问的值？是否有更简单的方法？
因为此扫描执行 \(|\mathbf{V}|\) 次，
并且因为每条边需要对 D 进行常数时间更新，
此方法的总成本为
\(\Theta(|\mathbf{V}|^2 + |\mathbf{E}|) =
\Theta(|\mathbf{V}|^2)\)，
因为 \(|\mathbf{E}|\) 在 \(O(|\mathbf{V}|^2)\) 中。
待处理
- type: AV
此处有 AV 演示 minVertex 的实现。
另一种方法是将未处理的顶点存储在按距离排序的最小堆中。
下一个最近的顶点可以在
\(\Theta(\log |\mathbf{V}|)\) 时间内在堆中找到。
每次我们修改 \(\mathbf{D}(X)\) 时，
我们可以通过删除并重新插入它来在堆中重新排列 \(X\)。
这是 优先队列 的一个例子，
具有优先级更新功能。
要实现真正的优先级更新，我们需要存储每个顶点
在堆中的位置，
以便在通过处理新边更新时可以删除其旧距离。
更简单的方法是将给定顶点的
新（始终更小的）距离值作为新记录添加到堆中。
当前在堆中给定顶点的最小值将首先被找到，
以后找到的较大数据值将被忽略，
因为该顶点将已被标记为 VISITED。
以这种方式重复插入距离值的唯一缺点是
它将使堆中的元素数量从
\(\Theta(|\mathbf{V}|)\) 增加到 \(\Theta(|\mathbf{E}|)\)
（在最坏情况下）。
但在实践中这只增加了堆深度的轻微增加。
时间复杂度为
\(\Theta((|\mathbf{V}| + |\mathbf{E}|) \log |\mathbf{E}|)\)，
因为我们处理的每条边都必须重新排列堆。
我们使用 KVPair 类在堆中存储键值对，
其中边权值为键，目标顶点为值。
以下是使用堆的 Dijkstra 算法实现。
// Dijkstra's shortest-paths: priority queue version
static void DijkstraPQ(Graph G, int s, int[] D) {
int v; // The current vertex
KVPair[] E = new KVPair[G.edgeCount()]; // Heap for edges
E[0] = new KVPair(0, s); // Initial vertex
MinHeap H = new MinHeap(E, 1, G.edgeCount());
for (int i=0; i<G.nodeCount(); i++) { // Initialize distance
D[i] = INFINITY;
}
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // For each vertex
KVPair temp = (KVPair)(H.removemin());
if (temp == null) { return; } // Unreachable nodes exist
v = (Integer)temp.value();
while (G.getValue(v) == VISITED) {
temp = (KVPair)(H.removemin());
if (temp == null) { return; } // Unreachable nodes exist
v = (Integer)temp.value();
}
G.setValue(v, VISITED);
if (D[v] == INFINITY) { return; } // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w))) { // Update D
D[w] = D[v] + G.weight(v, w);
H.insert(new KVPair(D[w], w));
}
}
}
}
// Dijkstra's shortest-paths: priority queue version
static void DijkstraPQ(Graph G, int s, int[] D) {
int v; // The current vertex
KVPair[] E = new KVPair[G.edgeCount()]; // Heap for edges
E[0] = new KVPair(0, s); // Initial vertex
MinHeap H = new MinHeap(E, 1, G.edgeCount());
for (int i=0; i<G.nodeCount(); i++) { // Initialize distance
D[i] = INFINITY;
}
D[s] = 0;
for (int i=0; i<G.nodeCount(); i++) { // For each vertex
KVPair temp = (KVPair)(H.removemin());
if (temp == null) { return; } // Unreachable nodes exist
v = (Integer)temp.value();
while (G.getValue(v) == VISITED) {
temp = (KVPair)(H.removemin());
if (temp == null) { return; } // Unreachable nodes exist
v = (Integer)temp.value();
}
G.setValue(v, VISITED);
if (D[v] == INFINITY) { return; } // Unreachable
int[] nList = G.neighbors(v);
for (int j=0; j<nList.length; j++) {
int w = nList[j];
if (D[w] > (D[v] + G.weight(v, w))) { // Update D
D[w] = D[v] + G.weight(v, w);
H.insert(new KVPair(D[w], w));
}
}
}
}
待处理
- type: Slideshow
此幻灯片使用堆演示 Dijkstra 算法。起始顶点为 A。除 A 外的所有顶点初始值均为 \(\infty\) 。处理顶点 A 后，其邻居的 D 估计值更新为从 A 出发的直接距离。处理 C（距 A 最近的顶点）后，顶点 B 和 E 被更新以反映经过 C 的最短路径。剩余顶点按 B、D 和 E 的顺序处理。D 数组的变化应随之显示。
当图是稠密图时，即 \(|\mathbf{E}|\) 接近 \(|\mathbf{V}|^2\) 时，使用 MinVertex 扫描顶点列表以查找最小值更为高效。当图是稀疏图时，使用堆更为高效，因为其成本为 \(\Theta((|\mathbf{V}| + |\mathbf{E}|) \log |\mathbf{E}|)\) 。然而，当图是稠密图时，此成本可能高达 \(\Theta(|\mathbf{V}|^2 \log |\mathbf{E}|) = \Theta(|V|^2 \log |V|)\) 。
待处理
- type: Slideshow
用于演示两种算法相对成本的幻灯片。
现在你可以练习使用 Dijkstra 算法。
待处理
- type: Exercise
Dijkstra 算法的总结性测试题
