- Bellman-Ford算法
- SPFA(Shortest Path Faster Algorithm)算法
Bellman-Ford算法
贝尔曼-福特算法是求解单源最短路径问题的一种算法。
原理是对图进行V-1次松弛操作，得到所有可能的最短路径。
其优于Dijkstra算法的方面是支持负权边、实现简单，缺点是时间复杂度过高，高达O(VE)。V为顶点的个数，E为边的个数。
实现方式是通过m次迭代求出从源点到终点不超过m条边构成的最短路的路径。
一般情况下要求途中不存在负环。
但是在边数有限制的情况下允许存在负环。
因此Bellman-Ford算法是可以用来判断负环的。
专用处理可能存在负环的有限路线单源最短路问题。
算法步骤
- 初始化：将除源点外的所有顶点的最短距离估计值 dist[v] ← +∞, dist[s] ←0;
- 迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
- 检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 dist[v]中。
有向图的测试代码：
#include<iostream>
#include<cstdio>
using namespace std;#define MAX 0x3f3f3f3f
#define N 1010
int nodenum, edgenum, original; //点，边，起点typedef struct Edge //边
{
int u, v;int cost;
}Edge;Edge edge[N];
int dis[N], pre[N];bool Bellman_Ford()
{
for(int i = 1; i <= nodenum; ++i) //初始化dis[i] = (i == original ? 0 : MAX);for(int i = 1; i <= nodenum - 1; ++i)for(int j = 1; j <= edgenum; ++j)if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反~）{
dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;pre[edge[j].v] = edge[j].u;}bool flag = 1; //判断是否含有负权回路for(int i = 1; i <= edgenum; ++i)if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost){
flag = 0;break;}return flag;
}void print_path(int root) //打印最短路的路径（反向）
{
while(root != pre[root]) //前驱{
printf("%d-->", root);root = pre[root];}if(root == pre[root])printf("%d\n", root);
}int main()
{
scanf("%d%d%d", &nodenum, &edgenum, &original);pre[original] = original;for(int i = 1; i <= edgenum; ++i){
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);}if(Bellman_Ford())for(int i = 1; i <= nodenum; ++i) //每个点最短路{
printf("%d\n", dis[i]);printf("Path:");print_path(i);}elseprintf("have negative circle\n");return 0;
}
SPFA(Shortest Path Faster Algorithm)算法
求单源最短路径。
是Bellman-ford的队列优化。高效。
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。SPFA的复杂度大约是O(kE),k是每个点的平均进队次数(一般的，k是一个常数，在稀疏图中小于2)。
但是，SPFA算法稳定性较差，在稠密图中SPFA算法时间复杂度会退化。
一般可以从题目看出有无负权边，若仅正权边，首选堆优化的dijkstra。
实现方法：
建立一个队列，初始时队列里只有起始点。
建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到它本身的路径赋为0）。
然后执行松弛操作，用队列里有的点去刷新起始点到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。
重复执行直到队列为空。
此外，SPFA算法还可以判断图中是否有负权环，即一个点入队次数超过N。
朴素SPFA算法模板
#include <stdio.h>
#include <string.h>const int N = 1010, M = 2e6, INF = 1e9;int n, m; //n是节点数，m是边数
int dist[N], q[N]; //dist[i]表示源点到i点的最短距离
int h[N], to[M], w[M], ne[M], idx; //idx初始化为0
bool st[N]; //储存每个点是否在队列中//添加边表示a到b有一条单向边，权值为c
void add(int a, int b, int c)
{
to[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}//求源点s到其它点的最短路径
void spfa(int s)
{
int hh, tt; //队列头指针和尾指针memset(st, false, sizeof(st));for(int i = 1; i <= n; i++) dist[i] = INF;dist[s] = 0;q[tt++] = s;st[s] = true;while(hh != tt){
//队列不为空int t = q[hh++];st[t] = false;if(hh == N) hh = 0;for(int i = h[i]; ~i; i = ne[i]){
if(dist[t] + w[i] < dist[to[i]]){
dist[to[i]] = dist[t] + w[i];if(!st[to[i]]){
st[to[i]] = true;q[tt++] = to[i];if(tt == N) tt = 0;}}}}
}int main()
{
int a, b, c;scanf("%d %d %d", &n, &m, &s);memset(h, -1, sizeof(h));for(int i = 1; i <= m; i++){
scanf("%d %d %d", &a, &b, &c);add(a, b, c);}spfa(s);for(int i = 1; i <= n; i++){
if(dist[i] == INF) puts("NO PATH");else printf("%d\n", dist[i]);}return 0;
}SLF优化的SPFA算法(有被卡到指数级的风险)
SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
#include <stdio.h>
#include <string.h>
#include <deque>
using namespace std;const int N = 1010, M = 2e6, INF = 1e9;int dist[N];
int h[N], to[M], w[M], ne[M], idx;
bool st[N];
int n, m;void add(int a, int b, int c)
{
to[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa(int s)
{
memset(st, false, sizeof(st));for(int i = 1; i <= n; i++) dist[i] = INF;dist[s] = 0;deque<int> q;q.push_front(s);st[s] = true;while(!q.empty()){
int t = q.front();q.pop_front();st[t] = false;for(int i = h[t]; ~i; i = ne[i]){
if(dist[t] + w[i] < dist[to[i]]){
dist[to[i]] = dist[t] + w[i];if(!st[to[i]]){
if(!q.empty() && dist[to[i]] < dist[q.front()])q.push_front(to[i]);else q.push_back(to[i]);st[to[i]] = true;}}}}
}