简介

最短路顾名思义就是求两个点之间的最短距离，在一些题中是非常重要的工具，一般根据不同的情况和限制需使用合适的算法（比如如果有负边权就不能用 \(dijkstra\)），一般分为单元最短路和多源最短路。最经典的算法有 \(dijkstra\)，\(floyd\)，\(bellman-ford\) 等。

在学习最短路之前，必须了解一些基本概念，本文不在赘述。

Bellman–Ford 算法

简介及基本用途

\(Bellman-ford\) 是很好理解的一种单源最短路算法，可以有负边权，这是它比较有优势的地方，但是它的时间复杂度并不占优，达到了 \(O(nm)\)，效率太低，又是单源最短路的算法，在比赛中不是很常见。但是它有一个别的最短路算法都没有的用处，就是可以判负环。闲话不多说已经不少了，开始吧。

小贴士：一般有负边权的图都是单向的，否则只要有负边一定就有负环了。

过程

• 我们知道两个点之间的简单路径经过的边的数量最多是 \(n - 1\)，所以我们可以做 \(n - 1\) 次以下操作（下面的 \(dp_i\) 表示 点 \(i\) 的答案）即可得到答案：

  • 枚举每条边 \([u, v, w]\)，执行 \(dp_v = \min(dp_v, dp_u + w)\)，也就是通过这条边更新两个点的答案，形式的说就是我们要求起点 \(S -> v\) 的答案，可以通过 \(S->u\) 的答案 \(+ w\) 转移过来。

• 因为这样一定能把一个点的答案转移到另一个点上去，也就可以求出每个点的答案。

• 而我们上面说到这个算法可以判负环（前提是整个图联通），现在我们来解释一下：因为如果没有负环，那么进行 \(n - 1\) 次上述操作后，答案一定确定下来了，否则一定会经过重复的点，什么情况才有这种情况呢？那就是有负环的时候，所以我们只用再做一次上面的操作，如果答案更新了，那就有负环了。

• 其实 Bellan-ford 也是一种 \(DP\)，拓扑序就是第一维枚举走了几条边，只是因为我们只用求最短路就省去了这一维。

时间复杂度

这东东复杂度共 \(n - 1\) 次操作，每次操作需枚举每条边进行转移，共 \(O(m)\)。

Code

const int MAXN = 5005, MAXM = 1e4 + 5;

struct Edge {
  int u, v, w;
} a[MAXM];

int n, m, dp[MAXN]; // 记得初始化

void Bellman-ford() {
  dp[1] = 0; // 假设 1 为起点
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= m; j++) {   // 枚举边进行转移
      dp[a[i].v] = min(dp[a[i].v], dp[a[i].u] + a[i].w);
    }
  }
  bool flag = 1;
  for (int i = 1; i <= m; i++) { // 判负环
    if (dp[a[i].v] > dp[a[i].u]) { // 出现负环
      flag = 0; 
    }
  }
}

Dijkstra 算法

简介及基本用途

\(dijkstra\) 算法是由荷兰计算机科学家 E. W. Dijkstra 于 \(1956\) 年发现，\(1959\) 年公开发表，简称 \(dij\)，是一种经典的在非负权图上的单源最短路算法（有点小贪心），边权必须非负!!! 否则这种算法将会出现问题。

过程

• \(dijkstra\) 的算法思想有点像 \(BFS\)，本身 \(BFS\) 就能求最短路，思想就是从小的答案开始一层一层往外扩散，这就是为什么 \(dij\) 的边权必须非负的原因。

• 但是我们知道 \(BFS\) 的边权是固定的，但是 \(dij\) 就不一定了。每次怎么找到答案最小的进行转移呢？根据不同的方法，时间复杂度也会不同，以下介绍最经典的两种。

  • 第一种就是暴力寻找当前答案最小的那个点进行转移，再进行转移，这是最简单直接的办法。

  • 显然上面的暴力有时候是应付不了的，如果我们要找的答案最小的点，就可以把所有转移到的状态记录下来，从里面找最小的，这个过程一般用优先队列实现。每次转移是把新的状态入队，从里面找出最小的进行转移，循环往复。

• 另外每个点一定只有从最优状态转移才最有效，也就是其他状态全部无效，所以如果一个点已经被转移过了就无须就行转移了。

正确性证明

简而言之，我们就是要证明我们现在找到的答案最小的点 \(x\)，它的答案一定不会比当前更优。其实这个问题很简单，因为我们知道边权是非负的，所以如果有一个点的答案没比当前点答案更有，转移过来也不可能比 \(x\) 的答案更优，而我们知道当前我们找到的是当前最优的状态转移，不可能有比当前状态更有的状态， 所以这个算法是完全成立的。

时间复杂度

暴力

每次寻找最小的点转移，共 \(n\) 次，这里是 \(O(n^2)\)，转移 \(O(m)\)，共 \(O(n^2)\)。

优先队列

因为一个点可能被多次更新时，而之前的无用状态可能还在优先队列里，不能将其挤出去，所以队列里的元素数量有 \(O(m)\) 个级别，总时间复杂度：\(O(m \log m)\)。

对比

经过对比我们发现在一些稠密图情况下，\(m = n^2\)，暴力反而更有优势。令外 Dijkstar 对比 Bellman–Ford 时间复杂度占优势，但是 Bellman–Ford 的优势在于可以有负边权，还可以判负环。

下面挂一下伪代码

暴力 Code

struct Edge {
  int x, w;
};

bool v[MAXN] = {0, 1};
int n, m, d[MAXN] = {INF}; // 需初始化
vector<Edge> g[MAXN];

void dij() { // 假设起点是 1
  for (int i = 2, x = 1; i <= n; i++) {
    int y = 0;
    for (auto e : g[x]) { // 转移
      d[e.x] = min(d[e.x], d[x] + e.w);
    }
    for (int i = 1; i <= n; i++) { // 求当前的最小答案
      if (!v[i] && d[i] < d[y]) {
        y = i;
      }
    }
    x = y, v[x] = 1;
  }
}

优先队列 Code

struct Edge { // 边
  int x, w;
};

struct Node { // 状态
  int x, w;  // 点的编号和距离
};

struct cmp {
  bool operator ()(const Node &i, const Node &j) {
    return i.w > j.w;
  }
};

bool v[MAXN];
int n, m, d[MAXN]; // 需初始化最大值
vector<Edge> g[MAXN];
priority_queue<Node, vector<Node>, cmp> pq; // 优先队列

void Record(int x, int w) {
  if (d[x] > w) { // 当前转移比当前点答案更有
    d[x] = w;  // 更新答案
    pq.push({x, w}); // 入队
  }
}

void dij() { // 假设起点是 1
  for (Record(1, 0); !pq.empty(); ) {
    Node u = pq.top(); pq.pop();
    if (v[u.x]) continue; // 已经转移过了
    for (auto e : g[u.x]) { // 转移
      Record(e.x, u.w + e.w);
    }
  }
}

未完待续。。。