[知识点]SPFA算法

时间:2023-03-09 08:26:39
[知识点]SPFA算法

// 此博文为迁移而来,写于2015年4月9日,不代表本人现在的观点与看法。原始地址:http://blog.sina.com.cn/s/blog_6022c4720102vx93.html

1、前言
       最短路算法有很多种,类似于Floyd和Dijkstra都是很早之前就学了的。其实每种最短路算法有各自的优势。Floyd适合于跑完全图,但是效率太慢(O(n3))。Dijkstra适合于跑没有负权的图,效率为O(n2)。而今天介绍的SPFA算法,是有一位中国人——段凡丁所提出来的(其实我很想吐个槽。。为什么人家弗洛伊德大叔提出了算法就叫弗洛伊德算法,迪杰斯特拉大爷提出的东西就叫迪杰斯特拉算法,段凡丁提出来的算法就变成了什么鬼SPFA(Shortest Path Faster Algorithm)。。严重的歧视啊。。。)
       其实SPFA没什么要讲的。看了一下模板就瞬间懂了。
2、概念
       SPFA算法,是队列实现的Bellman-Ford算法。非常好理解,都知道BFS跑无权迷宫吧?其实SPFA可以直接理解为BFS跑有权图。因为它的形式和BFS太像了。大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素,并对所有与他相邻的点进行松弛(松弛的意思自行脑补吧,看了程序就懂了),若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。先上代码:
//代码更新于20160916
#include <cstdio>
#include <cstring> #define MAXN 10000
#define MAXM 100000
#define INF 0x3f3f3f3f int T, n, m, u, v, w;
int h[MAXN], q[MAXN], o, dis[MAXN], vis[MAXN], s, t; struct Edge {
int v, next, w;
} edge[MAXM * ]; void addEdge(int u, int v, int w) {
edge[++o] = (Edge) {v, h[u], w}, h[u] = o;
} int SPFA(int s, int t) {
int head = , tail = ;
while (head != tail) {
int o = q[head];
for (int x = h[o]; x; x = edge[x].next) {
int v = edge[x].v;
if (dis[o] + edge[x].w < dis[v]) {
dis[v] = dis[o] + edge[x].w;
if (!vis[v]) q[tail++] = v, vis[v] = ;
}
}
vis[o] = ;
head++;
}
return dis[t];
} int main() {
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w), addEdge(v, u, w);
}
scanf("%d", &T);
for (int i = ; i <= T; i++) {
memset(vis, , sizeof(vis)), memset(dis, INF, sizeof(dis));
scanf("%d %d", &s, &t);
dis[s] = , vis[s] = , q[] = s;
printf("%d", SPFA(s, t));
}
return ;
}
       初始化:设dis[i]代表目前源点到i点的最短距离,开始时dist全部为INF(无穷大),只有dis[s]=0。
       SPFA:维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点s。用一个vis[i]记录i点是否处在队列中。每次迭代,取出队头的点v,依次枚举从v出发的边v->u,设边的长度为len,判断dis[v]+len是否小于dis[u],若小于则改进dis[u],并且由于s到u的最短距离变小了,有可能u可以改进其它的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是s到所有点的最短距离都确定下来,结束算法。
       备注:SPFA还有一个很强大的功能,可以判负权环。若一个点入队次数超过n,则有负权环。