5. 最短路径问题¶

5.1. 最短路径问题¶

在路线图上，连接两个城镇的道路通常标注其距离。我们可以将道路网络建模为有向图，其中边用实数标记。这些数字表示两个顶点之间的距离（或其他代价度量，如行程时间）。这些标签根据应用可以称为权值、代价或距离。给定这样一个图，一个典型问题是找到两个指定顶点之间最短路径的总长度。这不是一个简单的问题，因为最短路径可能不在连接两个顶点的边上，而是可能经过一个或多个中间顶点。

例如，在图 14.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。在图 14.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\)，因为图 14.5.1 是有向的。我们假设所有权值为正。

5.1.1. 单源最短路径¶

我们现在将介绍解决单源最短路径问题的算法。给定图 \(\mathbf{G}\) 中的顶点 \(S\)，找到从 \(S\) 到 \(\mathbf{G}\) 中每个其他顶点的最短路径。我们可能只需要两个顶点 \(S\) 和 \(T\) 之间的最短路径。然而在最坏情况下，找到从 \(S\) 到 \(T\) 的最短路径要求我们找到从 \(S\) 到每个其他顶点的最短路径。因此，在最坏情况下，找到到单个顶点的最短路径的算法与找到到所有顶点的最短路径一样好。这里描述的算法只计算到每个顶点的距离，而不是记录实际路径。记录路径只需要对算法进行简单的修改。

计算机网络提供了单源最短路径问题的应用。目标是找到一种最便宜的方式，让一台计算机向网络上的所有其他计算机广播消息。网络可以用图来建模，边权值表示向邻居计算机发送消息的时间或代价。

对于无权图（或所有边具有相同代价的情况），可以使用简单的广度优先搜索找到单源最短路径。添加权值后，BFS 将不会给出正确答案。

当边具有不同权值时，解决此问题的一种方法是按固定顺序处理顶点。将顶点标记为 \(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\) 中。因此，

\[\mathbf{d}(S, X) = \min_{U \in \mathbf{S}}(\mathbf{d}(S, U) + \mathbf{w}(U, X)).\]

换句话说，从 \(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 将包含最短距离值。

Java
Java (Generic)

// 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);
      }
    }
  }
}

Settings

Saving...

Server Error
Resubmit

在每次遍历主 for 循环时找到具有最小距离值的未访问顶点这一关键问题有两个合理的解决方案。第一种方法是简单地遍历 \(|\mathbf{V}|\) 个顶点的列表以搜索最小值，如下所示：

Java
Java (Generic)

// 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;
}

因为此扫描执行 \(|\mathbf{V}|\) 次，并且因为每条边需要对 D 进行常数时间更新，此方法的总成本为 \(\Theta(|\mathbf{V}|^2 + |\mathbf{E}|) = \Theta(|\mathbf{V}|^2)\)，因为 \(|\mathbf{E}|\) 在 \(O(|\mathbf{V}|^2)\) 中。

另一种方法是将未处理的顶点存储在按距离排序的最小堆中。下一个最近的顶点可以在 \(\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 算法实现。

Java
Java (Generic)

// 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));
      }
    }
  }
}

当图是稠密图时，即 \(|\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|)\) 。

现在你可以练习使用 Dijkstra 算法。

CS3 数据结构与算法

Chapter 14 Graphs

5. 最短路径问题¶

5.1. 最短路径问题¶

5.1.1. 单源最短路径¶