SPFA 算法

/**
    SPFA: Shortest Path Faster Algorithm
    看到名字不禁为之一颤，SPFA算法是西南交通大学段凡丁于1994年发表的。
    SPFA 也是竞赛中最常见的算法之一，不仅仅用来解决带负权的单源最短路
    而且是求解差分约束问题的专用算法，也常用它和最大流合作解决最小费问题
    可以说SPFA 是 dijkstra 和 bellman 的结合体，功能可见一斑……

    SPFA 算法的最坏复杂度为 O(2*E)。。

    SPFA 和dijkstra 格式很接近，只是加了个队列或栈就变得无比神奇了。

    这里用邻接表形式写下spfa 的模板

    后面再介绍它的其它功能，这里只知道它和bellman 功能一样，仅仅快即可
*/

const int inf = 0x3f3f3f3f;
const int nMax = 1000;
const int eMax = 500000;

struct {
    int v, w, next;
}edge[eMax];

int edgeHead[nMax], dis[nMax], n, ne; //n为点的个数, ne添边所用 //初始化edgeHead = 0 ne > 0
int vis[nMax], queue[nMax]; /**  stack[nMax] */  //替换queue

void addEdge(int u, int v, int w) {
    edge[ne].v = v;
    edge[ne].w = w;
    edge[ne].next = edgeHead[u];
    edgeHead[u] = ne++;
}

int spfa(int s, int t) {
    int i, head=0, tail=1 ; /** top = 0 */      //替换head , tail
    for (i=0; i<=n; i++) {
        dis[i] = inf;
        vis[i] = false;
    }
    dis[s] = 0;
    queue[0] = s;

    while (tail != head) {     /** (top) */   //替换(tail != head)
        int u = queue[head++]; /** u = stack[top--] */ //替换
        vis[u] = true;    //这里可有可无……
        for (i=edgeHead[u]; i; i=edge[i].next) {
            int v = edge[i].v, w = edge[i].w;
            if (dis[v] > dis[u]+w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = true;
                    /******************/
                    queue[tail++] = v;
                    if (tail == nMax) //循环队列
                        tail = 0;
                    /** stack[++top] = v */  //替换
                }
            }
        }
        vis[u] = false;    //这里是必须得有
        /****************/
        if (head == nMax)  //stack不需要噢，循环队列

            head = 0;
        /****************/   //替换删除
    }

    return dis[t];
}

/**
    注意: 添边时初始化 edgeHead = 0, ne > 0
          将标有替换的地方替换则变为栈操作
    判断正负权回路时，如果某点进入队列或栈的次数超过n 次则存在环
    只需用cnt[nMax] 数组标记每个点进入队列次数即可

    超级注意，只所以提供队列和栈两种操作是因为有些题卡队列，有些题卡堆栈
    不过肯定有一种能过，这种情况经常遇到，要注意啊!!!!!!!!!!!!
*/

收藏于 2011-11-25
来自于百度空间