Skip to content

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;
}
  • 可以用来解差分约束问题

习题