最短路

Floyd 多源最短路径

引入

Floyd 利用了 dp 的思想，主要可以用来求任意两个节点的连通性或最短路，可以有负边权，但不能有负环。

例题：luogu B3647 【模板】Floyd

我们设 \(f_{k,i,j}\) 为除了 \(i\) 和 \(j\) 外只经过前 \(k\) 个结点，从 \(i\) 到 \(j\) 的最短路，\(w_{i,j}\) 表示初始时给我们的从 \(i\) 到 \(j\)的边权。显然 \(f_{0,i,j}=w_{i,j}\)。那么当加⼊了⼀个顶点 \(k\) 之后，最短路如果有变化的话⼀定是以 \(k\) 为中间顶点，那么可以得到 \(f_{k,i,j}=\min\{f_{k-1,i,j},f_{k−1,i,k}+f_{k−1,k,j}\}\)。同时，可以利用滚动数组优化掉第一维，因为，首先在利用中间节点k更新距离的时候，\(f_{i,k}\) 和 \(f_{k,j}\) 的值肯定不会被更新，也就是k作为端点的情况，值不会发生改变。其次，即使我们遇到 \(k=j\) 的情况 \(f_{i,j}=\min\{f_{i,j},f_{i,j}+f_{j,j}\}\)，此处利用 \(f_{i,j}\) 递推 \(f_{i,j}\) 不会改变 \(f_{i,j}\)。
所以第一重循环枚举中间节点 \(k\)，第二重、第三重分别枚举 \(i,j\)，转移方程是：

\[f_{i,j}=\min\{f_{i,j},f_{i,k}+f_{k,j}\} \]

由于求的是最小值，所以边界是 \(f_{i,j}=+\infty,f_{i,i}=0\)。

点击查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, dis[4005][4005], u, v, w, ans = 0;
inline ll read() {
  ll x = 0, f = 1;
  char ch = getchar();
  while(!isdigit(ch))	{
    if(ch == '-') {
      f = -1;
    }
    ch = getchar();
  }
  while(isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
inline void write(ll x) {
  if(x < 0) {
    putchar('-');
    x = -x;
  }
  if(x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + '0');
}
int main() {
  n = read(), m = read();
  memset(dis, 0x3f, sizeof(dis));
  while(m--) {
    u = read(), v = read(), w = read();
    dis[v][u] = dis[u][v] = min(dis[u][v], w);
  }
  for(int i = 1; i <= n; i++) {
    dis[i][i] = 0;
  }
  for(int x = 1; x <= n; x++) {
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= n; j++) {
        dis[i][j] = min(dis[i][x] + dis[x][j], dis[i][j]);
      }
    }
  }
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      cout << dis[i][j] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

Bellman-Ford 单源最短路径

引入

Bellman-Ford 算法是一种基于松弛操作的单源最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。

过程

对于边 \((u,v)\)，松弛操作对应的式子：\(dis(v)=min(dis(v),dis(u)+w(u,v))\)。我们尝试用 \(S\to u \to v\)（其中\(S \to u\) 的路径取最短路）这条路径去更新 \(v\) 节点最短路的长度，如果这条路径更优，就进行更新。Bellman-Ford 算法所做的，就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。每次循环是 \(\mathcal{O}(m)\) 的，那么最多会循环多少次呢？在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少加 \(1\)，而最短路的边数最多为 \(n-1\)，因此整个算法最多执行 \(n-1\) 轮松弛操作。故总时间复杂度为 \(\mathcal{O}(n\times m)\)。但还有一种情况，如果从 \(S\) 点出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 \(n-1\) 轮，因此如果第 \(n\) 轮循环时仍然存在能松弛的边，说明从 \(S\) 点出发，能够抵达一个负环。需要注意的是，以 \(S\) 点为源点跑 Bellman-Ford 算法时，如果没有给出存在负环的结果，只能说明从 \(S\) 点出发不能抵达一个负环，而不能说明图上不存在负环。因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 \(0\) 的边，然后以超级源点为起点执行 Bellman-Ford 算法。

点击查看 Bellman-Ford 判负环的代码

inline bool bellmanford(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  bool flag = 0;
  for(int i = 1; i <= n; i++) {
    flag = 0;
    for(int u = 1; u <= n; u++) {
      if(dis[u] == 1e9) {
        continue;
      }
      for(auto ed : e[u]) {
        int v = ed.v, w = ed.w;
        if(dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          flag = 1;
        }
      }
    }
    if(!flag) {
      break;
    }
  }
  return flag;
}

SPFA 单源最短路径

在 Bellman-Ford 的基础上加一个队列进行优化。很多时候我们并不需要那么多无用的松弛操作。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护「哪些结点可能会引起松弛操作」，就能只访问必要的边了。同样也是松弛 \(n-1\) 轮即可，所以 SPFA 最坏情况下会退化成 Bellman-Ford。

点击查看 SPFA 判负环代码

inline bool spfa() {
  queue<int> q;
  for(int i = 1; i <= n; i++) {
    dis[i] = INT_MAX;
    vis[i] = 0;
  }
  q.push(1);
  dis[1] = 0;
  vis[1] = 1;
  ++cnt[1];
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for(int i = h[u]; i; i = e[i].ne) {
      int v = e[i].to;
      if(dis[v] > dis[u] + e[i].dis) {
        dis[v] = dis[u] + e[i].dis;
        if(!vis[v]) {
          vis[v] = 1;
          q.push(v);
          ++cnt[v];
          if(cnt[v] > n) {
            return 1;
          }
        }
      }
    }
  }
  return 0;
}

Dijkstra 单源最短路径

引入

Dijkstra 是一种在没有非负边权的图上求单源最短路径的算法，基于贪心的思想，所以不能有非负边权。

过程

将结点分成两个集合：已确定最短路长度的点集（记为S集合）的和未确定最短路长度的点集（记为 \(T\) 集合）。一开始所有的点都属于 \(T\) 集合。然后重复这些操作：从 \(T\) 集合中，选取一个最短路长度最小的结点，移到 \(S\) 集合中。对那些刚刚被加入 \(S\) 集合的结点的所有出边执行松弛操作。直到 \(T\) 集合为空，算法结束。

例题：luogu P4779 【模板】单源最短路径（标准版）

方法一：朴素做法

不加任何优化，时间复杂度 \(\mathcal{O}(n^2+m)=\mathcal{O}(n^2)\)，显然过不了，代码如下：

inline void dijkstra(int n, int s) {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  for(int i = 1; i <= n; i++) {
    int u = 0, mini = 0x3f3f3f3f;
    for(int j = 1; j <= n; j++) {
      if(!vis[j] && dis[j] < mini) {
        u = j;
        mini = dis[j];
      }
    }
    vis[u] = 1;
    for(auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if(dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
      }
    }
  }
}

方法二：手写二叉堆或优先队列

若用优先队列，如果同一个点的最短路被更新多次，因为先前更新时插入的元素不能被删除，也不能被修改，只能留在优先队列中，故优先队列内的元素个数是 \(\mathcal{O}(m)\) 的，时间复杂度为 \(\mathcal{O}(m\log_2 m)\)。
二叉堆的时间复杂度是 \(\mathcal{O}(m\log_2 n)\)，稍微比优先队列快一点，但优先队列代码好写亿点。