Bellman-Ford与SPFA

能支持负边的最短路径算法，但是比Dijkstra慢。

基本过程就是不断尝试对图上每一条边进行松弛。我们每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止。如果第 $n$ 轮循环时仍然存在能松弛的边，说明存的负环。复杂度 $O(nm)$ 。

一个更快的基于队列优化的变型是SPFA(Sortest Path Faster Algorithm)。很显然，只有上一次被松弛的结点，所连接的边，才有可能引起下一次的松弛操作。那么我们用队列来维护“哪些结点可能会引起松弛操作”，就能只访问必要的边了。

SPFA比Dijkstra实现更直观一些，而且可以解决有负边权的问题，但是最坏情况下复杂度还是 $O(nm)$ 。所以对于没有负边权的情况，还是应该用Dijkstra。

SPFA的实现：

struct edge {
  int v, w;
};
 
vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;
 
bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

可以用来解差分约束问题

习题
P3385		【模板】负环		普及/提高-
P1825	USACO Silver	Corn Maze		普及+/提高
P2176	USACO Gold	RoadBlock	2011	普及+/提高
P7100		团		普及+/提高
P4822	BJWC	冻结	2012	提高+/省选-
UVA11090	UVA	Going in Cycle!!		省选/NOI-