[知识点]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算法

相关文章