简介
Bellman-Ford算法是求解单源最短路的算法之一,适用于可包含负边权的有向和无向图,可以判断是否包含负环(注意,如果是包含负权回路则不存在最短路问题)。时间复杂度\(O(nm)\)。
Bellman-Ford算法
因为最短路径上最多有n-1条边,所以Bellman-Ford算法最多有n-1个阶段。在每一个阶段,我们对每一条边都要执行松弛操作。其实每实施一次松弛操作,就会有一些顶点已经求得其最短路,即这些顶点的最短路的“估计值”变为“确定值”。此后这些顶点的最短路的值就会一直保持不变,不再受后续松弛操作的影响(但是,每次还是会判断是否需要松弛)。在前k个阶段结束后,就已经找出了从源点出发“最多经过k条边”到达各个顶点的最短路。直到进行完n-1个阶段后,便得出了最多经过n-1条边的最短路。
核心代码如下:
1 2 3 4 5 6 7 8 9 10
| int bellman(int s, int n, int m) { dis[s] = 0; for(int k=1; k<n; k++){ for(int i=1; i<=m; i++){ dis[v[i]] = min(dis[v[i]], dis[u[i]]+w[i]); } } return 0; }
|
如果在n-1次松弛之后,还有可以进行松弛的边,那么就存在负环(负权回路):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| int bellman(int s, int n, int m) { dis[s] = 0; for(int k=1; k<n; k++){ for(int i=1; i<=m; i++){ if(dis[u[i]]+w[i] < dis[v[i]]){ dis[v[i]] = dis[u[i]]+w[i]; pre[v[i]] = u[i]; } } } for(int i=1; i<=m; i++){ if(dis[u[i]]+w[i] < dis[v[i]]){ return -1; } } return 0; }
|
SPFA
SPFA是Bellman-Ford算法的队列优化,核心思想,只有那些在前一遍松弛中改变了距离估计值的点,才可能引起它们的邻接点的距离估计值的改变。为什么队列为空就不改变了呢?就是因为要到下一点必须经过它的前一个邻接点。
设立一个先进先出的队列q用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
核心代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| int spfa(int s, int n) { dis[s] = 0; vis[s] = 1; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i=H[u]; ~i; i=e[i].next){ int v = e[i].to, w = e[i].w; if(dis[u]+w < dis[v]){ dis[v] = dis[u]+w; if(!vis[v]) q.push(v), vis[v] = 1; } } } return 0; }
|
其它优化
除了队列优化(SPFA)之外,Bellman-Ford 还有其他形式的优化,这些优化在部分图上效果明显,但在某些特殊图上,最坏复杂度可能达到指数级。
- 堆优化:将队列换成堆,与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
- 栈优化:将队列换成栈(即将原来的 BFS 过程变成 DFS),在寻找负环时可能具有更高效率,但最坏时间复杂度仍然为指数级。
- LLL 优化:将普通队列换成双端队列,每次将入队结点距离和队内距离平均值比较,如果更大则插入至队尾,否则插入队首。
- SLF 优化:将普通队列换成双端队列,每次将入队结点距离和队首比较,如果更大则插入至队尾,否则插入队首。
更多优化以及针对这些优化的 Hack 方法,可以看 fstqwq 在知乎上的回答 。
模板
Bellman-Ford算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
| const int inf = 0x3f3f3f3f; const int mxn = 1e3 + 5;
int u[mxn], v[mxn], w[mxn]; int dis[mxn], pre[mxn];
void bellman_init(int n) { for(int i=1; i<=n; i++){ dis[i] = inf; pre[i] = 0; } }
int bellman(int s, int n, int m) { int k=0, f=1; dis[s] = 0; while(f) { if(++k > n) return -1; f = 0; for(int i=1; i<=m; i++){ if(dis[u[i]]+w[i] < dis[v[i]]){ dis[v[i]] = dis[u[i]]+w[i]; pre[v[i]] = u[i]; f = 1; } } } return 0; }
int main() { int n, m; scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++) { scanf("%d %d %d", &u[i], &v[i], &w[i]); }
bellman_init(n); if(bellman(1, n, m) == -1) { printf("包含负权回路\n"); } else { for(int i=1; i<=n; i++) printf("%d ", dis[i]); printf("\n");
for(int i=1; i<=n; i++) printf("%d ", pre[i]); printf("\n"); }
return 0; }
|
SPFA:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| const int inf = 0x3f3f3f3f; const int mxn = 1e3 + 5;
struct E { int to, next, w; } e[mxn];
int H[mxn], tot;
void add(int from, int to, int w) { e[tot] = {to, H[from], w}; H[from] = tot++; }
void graph_init(int n) { for(int i=1; i<=n; i++) H[i] = -1; tot = 0; }
int dis[mxn], pre[mxn], num[mxn]; bool vis[mxn]; queue<int> q;
void spfa_init(int n) { for(int i=1; i<=n; i++){ dis[i] = inf; num[i] = pre[i] = 0; } }
int spfa(int s, int n) { dis[s] = 0; q.push(s); num[s] = vis[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for(int i=H[u]; ~i; i=e[i].next){ int v = e[i].to, w = e[i].w; if(dis[u]+w < dis[v]){ dis[v] = dis[u]+w; pre[v] = u; if(!vis[v]){ q.push(v), vis[v] = 1; if(++num[v] > n) return -1; } } } } return 0; }
int main() { int n, m; scanf("%d %d", &n, &m); graph_init(n);
for(int i=1; i<=m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); add(u, v, w); }
spfa_init(n); if(spfa(1, n) == -1) { printf("包含负权回路\n"); } else { for(int i=1; i<=n; i++) printf("%d ", dis[i]); printf("\n");
for(int i=1; i<=n; i++) printf("%d ", pre[i]); printf("\n"); }
return 0; }
|