Bellman-Ford与SPFA

Bellman-Ford与SPFA

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

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

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

SPFA比Dijkstra实现更直观一些,而且可以解决有负边权的问题,但是最坏情况下复杂度还是O(nm)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【模板】负环普及/提高-
P1825USACO SilverCorn Maze普及+/提高
P2176USACO GoldRoadBlock2011普及+/提高
P7100普及+/提高
P4822BJWC冻结2012提高+/省选-
UVA11090UVAGoing in Cycle!!省选/NOI-