Bellman-Ford单源最短路算法
不采用 SPFA 实现的Bellman-Ford算法
" 题目中的图没有特殊性质时，若 SPFA 是标算的一部分，题目不应当给出 Bellman–Ford 算法无法通过的数据范围 "
Bellman-Ford的原理如下
先枚举节点，在枚举边，每进行一轮循环，对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，退出循环
- 判断负环的存在 （有\(n\) 个节点）
对于最短路存在的情况下，对这个节点进行一次松弛操作会使最短路的边数至少增加 \(1\) ，又因为图上的最短路的边数最多为 \(n-1\)
所以松弛操作最多只会执行 \(n-1\) 轮
如果第 \(n\) 轮时我们还能对一条边进行松弛操作，说明能够到达一个负环，在这个环上没有最短路定义，可以一直松弛下去
struct edge {
int v, w; // 目标节点 v 和边权重 w
};
void init(void){
memset(dis,0x3f,sizeof dis);
}
bool bellman_ford(int s){
init();
dis[s]=0;
bool flag;
for (int i=1;i<=n;i++){//进行 n 轮
flag=0;
for (int u=1;u<=n;u++){//遍历所有节点
if (dis[u]==0x3f3f3f3f) continue;
for (auto it=e[u].begin();it!=e[u].end();it++){//遍历与u连通的边
if (dis[it->v]>dis[u]+it->w){//松弛操作
dis[it->v]=dis[u]+it->w;
flag=1;//标记这一轮可以松弛
}
}
}
if (!flag) break;//如果无法松弛，提前退出循环
}
return flag;//返回最后的标志，判断是否存在负环
}
其中，定义 flag 来判断是否能进行松弛操作，最后在第 \(n\) 轮时 flag 仍然为 \(1\) ，说明存在负环
if (dis[u]==0x3f3f3f3f) continue; 表示如果当前节点不能到达，那就跳过这个节点
- 时间复杂度判断
对于每轮循环，内层的两个 for 都在干一件事情，那就是更新所有的边，所以一轮的复杂度就为 \(O(m)\)，总的时间复杂度就为 \(O(nm)\)
优化方案——SPFA(Shortest Path Faster Algorithm)
朴素的算法中，我们会执行的不必要操作就是每轮都遍历所有的边
事实上，只有上一轮更新过的点才能引起这一轮的松弛操作，所以可以把上一轮更新的点记录下来，这一轮直接对这些点进行松弛操作
采用的是队列 queue 这一数据结构来维护更新的点
queue<int> q;
另外还需要cnt 和 vis 数组来记录当前节点最短路的边数以及是否在队中
bool vis[2010];
int cnt[2010];
SPFA：
bool spfa(int s) {
init();
dis[s] = 0;
q.push(s);
vis[s] = 1;
while (q.size())
{
int t = q.front(); q.pop();
vis[t] = 0;//取出队列
for (auto it = e[t].begin(); it != e[t].end(); it++) {
if (dis[it->v] > dis[t] + it->w) {
dis[it->v] = dis[t] + it->w;
cnt[it->v] = cnt[t] + 1;
if (cnt[it->v] >= n) return 1;//判断负环
if (!vis[it->v]) {//压入队列
q.push(it->v);
vis[it->v] = 1;
}
}
}
}
return 0;
}
首先将起点 s 压入队列，vis[s] = 1 表明在队中
- 循环直到队列为空，即不能松弛结束
- 根据最短路的边数来判断负环
如果一个点的最短路边数大于等于了节点数 n ，说明一定存在一个负环导致某些边的经过次数大于 \(1\) ，及时退出
如果当前的节点能够进行松弛操作，并且当前还不在队列中，就把他压入队列