最短路径算法基础

本文介绍四种最短路径算法以及其对应的模板。最短路径算法是十分基础的算法，一方面，一些题目直接需要我们求图中两点的最短路径；另一方面，一些题目也可以通过先建模成图，然后再调用最短路径算法解决。

本文要介绍的最短路径算法包括以下几种：

算法	限制	复杂度
Dijkstra算法	图中无负权边,单源	$O(n^2)$
Bellman-Ford算法	无限制，单源	$O(mn)$
SPFA算法	无限制，单源	一般$O(m)$ 最坏$O(mn)$
Floyd算法	多源	$O(n^3)$

Dijkstra算法

Dijkstra算法采用了一种贪心的算法，它维护一个当前已经求的最短路的集合，然后不断向其中添加点，直到所有点都被添加进去。而每次添加点的方式就是选择当前距离源点最近的点（贪心），而当一个点被加入了之后，就用这个点来更新其他与该点相连的点到源点的距离。

在代码实现上如下所示，我们使用二维矩阵g[N][N]来代表一个图，g[i][j]表示有向图中点i到点j的距离, 一共有n个点。

void dijkstra() {
  std::memset(dist, 0x3f, sizeof(dist));
  // Assume the source point is 1
  dist[1] = 0;
  // Loop until all 'n' nodes have been visited
  for (int run = 1; run <= n; ++run) {
    // Find an unvisited node that has minimal distance
    int min_node, min_dist = 1e9;
    for (int i = 1; i <= n; ++i) {
      if (dist[i] < min_dist && !visit[i]) {
        min_dist = dist[i];
        min_node = i;
      }
    }

    visit[min_node] = true;
    // Use newly-added node to update other distance
    for (int i = 1; i <= n; ++i) {
      if (!visit[i] && dist[i] > dist[min_node] + g[min_node][i]) {
        dist[i] = dist[min_node] + g[min_node][i];
      }
    }
  }
}

因为上述过程需要执行n轮，而且每轮都需要查找最短距离的点，并且用该点来更新另外n个点的距离，因此复杂度为$O(n^2)$.

上述算法被称为朴素的Dijkstra算法，一个优化版本是在搜索当前最短路径点的时候使用堆进行优化，这样查找最短路径点的复杂度从$O(n)$降低为$O(\log n)$. 这部分代码如下：

void dijkstra() {
  std::priority_queue<Point, std::vector<Point>> q;
  dist[1] = 0;
  q.push({1, 0});
  while(!q.empty()) {
    curr = q.top();
    q.pop();
    if (visit[curr.x]) {
      continue;
    }
    
    visit[curr.x] = true;
    dist[curr.x] = curr.dist;

    if (curr.x == n) {
      return dist[curr.x];
    }

    for (const auto& edge : g[curr.x]) {
      if (!visit[edge.x]) {
        dist[edge.x] = std::min(dist[edge.x], dist[curr.x] + edge.dist);
        q.push({edge.x, dist[edge.x]});
      }
    }
}

我们使用一个堆来存储所有点到源点的距离，但是值得注意的是该堆中可能存在多个目的点相同的点对，这是因为一个点可能多次被前面加入集合的点所更新过。但堆的性质保证了即使有多个点在堆中时，其top()调用也只会获得具有最小路径的那条记录。我们需要在第8行检查该点之前是否已经加入过最短路集合了。

---

Bellman-Ford算法

Dijkstra算法的一个限制时不能有负权，下面的一个例子说明了在有负权时Dijkstra算法会得到错误的结果：

/*
 *      4 
 *  a--------->b
 *   \       / 
 *    \ 5   / -3
 *     \   / 
 *      \ /
 *       c
 *  其中a指向c，c指向b，且c到b这条边是负权边。
 *  根据dijkstra算法，我们会先得到dist[b] = 4, 并且将visit[b]设置
 *  为true，但实际上从上图来看，dist[b] = 5 + (-3) = 2才对。
 */

原因在于Dijkstra算法一旦将一个点加入了最短路集合中就不会在后续继续更新该点的距离了，在所有边都是正权时，这样做并没有问题。但负权可能会在节点扩展到一定程度时导致原先的距离被进一步缩小。

为了解决这个问题，一个自然的想法是一直追踪点到源点的距离，追踪的方式就是利用其他点来更新该点到源点的最短距离。例如在上个例子中，持续追踪b和a之间的距离，可以使用c的距离5加上c到b的距离-3，得到更小的距离2。

根据上述原则我们可以写出以下的动态规划方程：

dist[i] = min(dist[i], dist[j] + edge[j][i]), 1 <= j <= n;

但是上述递推方程的问题在于，要更新dist[i], 必须要有dist[j]的信息，而要更新dist[j]也必须要有dist[i]的信息，这样就形成了互相依赖的关系，双方谁也无法计算出需要的值。

而Bellman-Ford算法巧妙地打破了这一依赖关系，他将问题转述如下：从源点到目的点，最多不超过k条边的最短路。通过这种方式，Bellman-Ford算法引入了第三个纬度，打破了依赖关系。在这种描述方式下，dist[i]只会依赖于上一轮的所有dist结果，因为从源点到目的点dst的不超过k条边的路径可以分为两类：

• 从源点到某个点tmp, 再从tmp到目的点dst,由于整个路径不超过k条边，因此前一部分不能超过k-1条边；
• 从源点直接到dst的不超过k-1条边的路径。

因此我们可以写出如下的动态规划方程：

dist[i][k] = min(dist[i][k - 1], dist[j][k - 1] + edge[j][i]), 1 <= j <= n;

代码如下所示：

void bellman_ford() {
  std::memset(dist, 0x7f, sizeof(dist));
  // move from 1 to 1 is of distance 0
  dist[1][0] = 0;
  for (int turn = 1; turn <= k; ++turn) {
    int prev = (turn - 1) % 2;
    // For each node, update the distance from the last run related 
    // node value. The update value in run turn only relies on value 
    // in the last run
    for (int j = 1; j <= n; ++j) {
      int val = dist[j][prev];
      for (const auto &edge : g[j]) {
        int src = edge.from, w = edge.weight;
        val = std::min(dist[src][prev] + w, val);
      }
      dist[j][turn % 2] = val;
    }
  }
}

由于第k轮的更新值只会依赖于第k-1轮的值，因此我们只需要一个二维数据dist[n][2]来保存dist[n][k]和dist[n][k - 1]即可。在更新时，对每个点，都按照上面的动态规划方程执行，这里我们存储边的方式是邻接表。g[j]代表了所有到达j的点；第12行的循环就是遍历了所有到达j的边，并用其源点上一轮的最短路径来更新当轮的最短路径。

使用Bellman-Ford算法可以用来判断图中是否有负环，一般而言从源点到目的点的最短路至多只会经历n-1条边，如果超过n条边，那么这条路径上有超过n+1个点，根据抽屉原理，必有两个点相同，那么如果我们将这两个相同点之间的路径拿掉，这条路径的长度会增加，否则与最短路的定义矛盾，因此这两个相同点之间的路径形成了一个负环。

Bellman-Ford算法的复杂度在上述代码中为$O(km)$, 因为我们执行了k轮，每轮都查看了所有点的入边，入边的大小正好等于$O(m)$.通常而言，我们会将$k$设为$n-1$, 这样Bellman-Ford算法的复杂度为$O(nm)$.

---

SPFA算法

Bellman-Ford算法通过引入第三个纬度解决了相互依赖问题，但是其复杂度较高，高达$O(nm)$, 对于一个稠密图，$m=O(n^2)$, 运行Bellman-Ford算法会导致$O(n^3)$的开销，因此Bellman-Ford算法的效率实际上较低。而造成Bellman-Ford算法效率低下的原因在于每一轮算法执行时都需要去遍历所有的边来更新最短路径。实际上，我们观察递推方程：

dist[i][k] = min(dist[i][k - 1], dist[j][k - 1] + edge[j][i]), 1 <= j <= n

我们可以发现，dist[i][k]的更新仅仅依赖于上一轮中的dist[j][k - 1]， 这里的j也只有那些与i相连的节点而已，因此，如果一个节点i的所有前驱j都没有更新，那么该节点i也不会被更新。SPFA算法正是基于这个观察，当一个节点i的最短路被更新时，它将自己push到一个队列中，用自己的最短路径来更新其后继节点的最短路径。

void spfa() {
  memset(dist, 0x7f, sizeof(dist));
  dist[1] = 0;
  in_q[1] = true;
  std::queue<int> q;
  q.push(1);
  // Loop unitl q is not empty
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    in_q[curr] = false;
    
    for (const auto& edge : g[curr]) {
      int64_t new_dist = dist[curr] + edge.weight;
      if (new_dist < dist[edge.to]) {
        dist[edge.to] = new_dist;
        // Push the node only when it is not in the queue
        if (!in_q[edge.to]) {
          q.push(edge.to);
          in_q[edge.to] = true;
        }
      }
    }
  }
}

SPFA算法在最坏情况下等同于Bellman-Ford算法，其复杂度为$O(mn)$, 但是在一般情况下其复杂度仅有$O(m)$.

---

Floyd算法

不同于上面的三种单源最短路径算法，Floyd算法用于求一个图中任意两点之间的最短路径，Floyd算法实际上也是动态规划的一个直接应用。在Floyd算法中，我们需要维护一个状态：dist[i][j][k], 即从i到j， 只经过1..k这些点的最短路径。

根据以上的定义，我们发现从i到j且只经过1..k这些点的路径可以分为两类：经过k的和不经过k的，如果经过k，那么其路径中必定存在一个点k, 该路径可分为从i到k和从k到j.如果不经过k，那么该路径是一条从i到j的只经过1..k-1的路径。

因此我们可以写出如下的递推方程：

dist[i][j][k] = min(dist[i][k][k] + dist[j][k][k], dist[i][j][k - 1]);

代码实现如下：

void floyd() {
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}

---