最短路徑之 SPFA算法 zz

Posted on 2009-10-30 14:00 小強(qiáng)摩羯座閱讀(2958) 評(píng)論(0) 編輯收藏所屬分類: 算法編程

最短路徑之 SPFA算法 (轉(zhuǎn)載）(2009-05-06 20:41:51)

標(biāo)簽：spfa 雜談

求最短路徑的算法有許多種，除了排序外，恐怕是OI界中解決同一類問(wèn)題算法最多的了。最熟悉的無(wú)疑是Dijkstra，接著是Bellman-Ford，它們都可以求出由一個(gè)源點(diǎn)向其他各點(diǎn)的最短路徑；如果我們想要求出每一對(duì)頂點(diǎn)之間的最短路徑的話，還可以用Floyd-Warshall。

SPFA是這篇日志要寫(xiě)的一種算法，它的性能非常好，代碼實(shí)現(xiàn)也并不復(fù)雜。特別是當(dāng)圖的規(guī)模大，用鄰接矩陣存不下的時(shí)候，用SPFA則可以很方便地面對(duì)臨接表。每個(gè)人都寫(xiě)過(guò)廣搜，SPFA的實(shí)現(xiàn)和廣搜非常相似。

如何求得最短路徑的長(zhǎng)度值？

首先說(shuō)明，SPFA是一種單源最短路徑算法，所以以下所說(shuō)的“某點(diǎn)的最短路徑長(zhǎng)度”，指的是“某點(diǎn)到源點(diǎn)的最短路徑長(zhǎng)度”。

我們記源點(diǎn)為S，由源點(diǎn)到達(dá)點(diǎn)i的“當(dāng)前最短路徑”為D[i]，開(kāi)始時(shí)將所有D[i]初始化為無(wú)窮大，D[S]則初始化為0。算法所要做的，就是在運(yùn)行過(guò)程中，不斷嘗試減小D[]數(shù)組的元素，最終將其中每一個(gè)元素減小到實(shí)際的最短路徑。

過(guò)程中，我們要維護(hù)一個(gè)隊(duì)列，開(kāi)始時(shí)將源點(diǎn)置于隊(duì)首，然后反復(fù)進(jìn)行這樣的操作，直到隊(duì)列為空：

(1)從隊(duì)首取出一個(gè)結(jié)點(diǎn)u，掃描所有由u結(jié)點(diǎn)可以一步到達(dá)的結(jié)點(diǎn)，具體的掃描過(guò)程，隨存儲(chǔ)方式的不同而不同；

(2)一旦發(fā)現(xiàn)有這樣一個(gè)結(jié)點(diǎn)，記為v，滿足D[v] > D[u] + w(u, v)，則將D[v]的值減小，減小到和D[u] + w(u, v)相等。其中，w(u, v)為圖中的邊u-v的長(zhǎng)度，由于u-v必相鄰，所以這個(gè)長(zhǎng)度一定已知（不然我們得到的也不叫一個(gè)完整的圖）；這種操作叫做松弛。

引用內(nèi)容

松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在信息學(xué)中我們叫它三角不等式。所謂對(duì)i,j進(jìn)行松弛，就是判定是否d[j]>d[i]+w[i,j]，如果該式成立則將d[j]減小到d[i]+w[i,j]，否則不動(dòng)。

(3)上一步中，我們認(rèn)為我們“改進(jìn)了”結(jié)點(diǎn)v的最短路徑，結(jié)點(diǎn)v的當(dāng)前路徑長(zhǎng)度D[v]相比于以前減小了一些，于是，與v相連的一些結(jié)點(diǎn)的路徑長(zhǎng)度可能會(huì)相應(yīng)地減小。注意，是可能，而不是一定。但即使如此，我們?nèi)匀灰獙加入到隊(duì)列中等待處理，以保證這些結(jié)點(diǎn)的路徑值在算法結(jié)束時(shí)被降至最優(yōu)。當(dāng)然，如果連接至v的邊較多，算法運(yùn)行中，結(jié)點(diǎn)v的路徑長(zhǎng)度可能會(huì)多次被改進(jìn)，如果我們因此而將v加入隊(duì)列多次，后續(xù)的工作無(wú)疑是冗余的。這樣，就需要我們維護(hù)一個(gè)bool數(shù)組Inqueue[]，來(lái)記錄每一個(gè)結(jié)點(diǎn)是否已經(jīng)在隊(duì)列中。我們僅將尚未加入隊(duì)列的點(diǎn)加入隊(duì)列。

算法能否結(jié)束？

對(duì)于不存在負(fù)權(quán)回路的圖來(lái)說(shuō)，上述算法是一定會(huì)結(jié)束的。因?yàn)樗惴ㄔ诜磸?fù)優(yōu)化各個(gè)最短路徑長(zhǎng)度，總有一個(gè)時(shí)刻會(huì)進(jìn)入“無(wú)法再優(yōu)化”的局面，此時(shí)一旦隊(duì)列讀空，算法就結(jié)束了。然而，如果圖中存在一條權(quán)值為負(fù)的回路，就糟糕了，算法會(huì)在其上反復(fù)運(yùn)行，通過(guò)“繞圈”來(lái)無(wú)休止地試圖減小某些相關(guān)點(diǎn)的最短路徑值。假如我們不能保證圖中沒(méi)有負(fù)權(quán)回路，一種“結(jié)束條件”是必要的。這種結(jié)束條件是什么呢？

思考Bellman-Ford算法，它是如何結(jié)束的？顯然，最樸素的Bellman-Ford算法不管循環(huán)過(guò)程中發(fā)生了什么，一概要循環(huán)|V|-1遍才肯結(jié)束。憑直覺(jué)我們可以感到，SPFA算法“更聰明一些”，就是說(shuō)我們可以猜測(cè)，假如在SPFA中，一個(gè)點(diǎn)進(jìn)入隊(duì)列——或者說(shuō)一個(gè)點(diǎn)被處理——超過(guò)了|V|次，那么就可以斷定圖中存在負(fù)權(quán)回路了。

最短路徑本身怎么輸出？

在一幅圖中，我們僅僅知道結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短路徑長(zhǎng)度是73，有時(shí)候意義不大。這附圖如果是地圖的模型的話，在算出最短路徑長(zhǎng)度后，我們總要說(shuō)明“怎么走”才算真正解決了問(wèn)題。如何在計(jì)算過(guò)程中記錄下來(lái)最短路徑是怎么走的，并在最后將它輸出呢？

Path[]數(shù)組，Path[i]表示從S到i的最短路徑中，結(jié)點(diǎn)i之前的結(jié)點(diǎn)的編號(hào)。注意，是“之前”，不是“之后”。最短路徑算法的核心思想成為“松弛”，原理是三角形不等式，方法是上文已經(jīng)提及的。我們只需要在借助結(jié)點(diǎn)u對(duì)結(jié)點(diǎn)v進(jìn)行松弛的同時(shí)，標(biāo)記下Path[v] = u，記錄的工作就完成了。

輸出時(shí)可能會(huì)遇到一點(diǎn)難處，我們記的是每個(gè)點(diǎn)“前面的”點(diǎn)是什么，輸出卻要從最前面往最后面輸，這不好辦。其實(shí)很好辦，見(jiàn)如下遞歸方法：

程序代碼

void PrintPath(int k){
if( Path[k] ) PrintPath(Path[k]);
fout<<k<<' ';
}

SPFA的代碼怎么寫(xiě)？

我寫(xiě)了鄰接表和鄰接矩陣兩種，兩者想像起來(lái)是那么的不同，算法的思路上實(shí)在區(qū)別不大，只是用不同方式詮釋“掃描”的過(guò)程而已。只給出SPFA的單個(gè)函數(shù)，我不覺(jué)得很容易看懂，但是我仍然把兩個(gè)程序的SPFA函數(shù)放在下面。在日志的結(jié)尾處，有一個(gè)完整版文件下載。貼程序，首先是鄰接表的：

程序代碼

void SPFA(){
    for(int i=1; i<=gv; i++)
        Dist[i] = 100000;
    Dist[S] = 0;
    int closed = 0, open = 1;
    queue[1] = S;
    Inqueue[S] = true;
    do{
        closed++;
        node *tmp = connect[queue[closed]];
        Inqueue[queue[closed]] = false;
        while(tmp != NULL){
            if( Dist[tmp->key] > Dist[queue[closed]] + tmp->w ){
                Dist[tmp->key] = Dist[queue[closed]] + tmp->w;
                Path[tmp->key] = queue[closed];
                if( !Inqueue[tmp->key] ){
                    Inqueue[tmp->key] = true;
                    open++;
                    queue[open] = tmp->key;
                }
            }
            tmp = tmp->next;
        }
    }while(closed < open);
}

然后是鄰接矩陣的：

程序代碼

void SPFA(){
    for( int i=1; i<=gv; i++){
        Dist[i] = 100000;
        for( int j=1; j<=gv; j++)
            if( !Graph[i][j] && i!=j) Graph[i][j] = 100000;
    }
    int closed = 0, open = 1;
    queue[1] = S;
    Dist[S] = 0;
    do{
        closed++;
        int u = queue[closed];
        Inqueue[u] = false;
        for(int i=1; i<=gv; i++)
            if ( Dist[i] > Dist[u] + Graph[u][i] ){
                Dist[i] = Dist[u] + Graph[u][i];
                Path[i] = u;
                if( !Inqueue[i] ){
                    Inqueue[i] = true;
                    open++;
                    queue[open] = i;
                }
            }
    }while(closed < open);
}

spfa算法 Easy sssp 收藏
輸入數(shù)據(jù)給出一個(gè)有N(2 <= N <= 1,000)個(gè)節(jié)點(diǎn)，M(M <= 100,000)條邊的帶權(quán)有向圖.
要求你寫(xiě)一個(gè)程序, 判斷這個(gè)有向圖中是否存在負(fù)權(quán)回路. 如果從一個(gè)點(diǎn)沿著某條路徑出發(fā), 又回到了自己, 而且所經(jīng)過(guò)的邊上的權(quán)和小于0, 就說(shuō)這條路是一個(gè)負(fù)權(quán)回路.
如果存在負(fù)權(quán)回路, 只輸出一行-1;
如果不存在負(fù)權(quán)回路, 再求出一個(gè)點(diǎn)S(1 <= S <= N)到每個(gè)點(diǎn)的最短路的長(zhǎng)度. 約定: S到S的距離為0, 如果S與這個(gè)點(diǎn)不連通, 則輸出NoPath.

INPUT:
第一行: 點(diǎn)數(shù)N(2 <= N <= 1,000), 邊數(shù)M(M <= 100,000), 源點(diǎn)S(1 <= S <= N);
以下M行, 每行三個(gè)整數(shù)a, b, c表示點(diǎn)a, b(1 <= a, b <= N)之間連有一條邊, 權(quán)值為c(-1,000,000 <= c <= 1,000,000)

OUTPUT:
如果存在負(fù)權(quán)環(huán), 只輸出一行-1, 否則按以下格式輸出
共N行, 第i行描述S點(diǎn)到點(diǎn)i的最短路:
如果S與i不連通, 輸出NoPath;
如果i = S, 輸出0;
其他情況輸出S到i的最短路的長(zhǎng)度

INPUT:
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

OUTPUT:
0
6
4
-3
-2
7

注意：
題目說(shuō)的不是很清楚，給出的圖不一定是完全聯(lián)通圖，有些是斷開(kāi)的幾個(gè)圖，所以在判斷的源點(diǎn)是否有環(huán)以外還要分別對(duì)不同的點(diǎn)進(jìn)行spfa呀。再進(jìn)行分別的判斷和輸出。

有幾個(gè)優(yōu)化：
1.可以先判斷是否有負(fù)權(quán)自環(huán)，有則直接輸出-1
2.在枚舉的過(guò)程中，當(dāng)這個(gè)頂點(diǎn)的最短路(d[i])<0時(shí)，有負(fù)權(quán)回路，輸出-1.

【參考程序】：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long queue[1001],a[1001],psum[1001],dis[1001],l[1001][1001],cost[1001][1001];
long n,m,s,i,j;
bool hash[1001],bk;
void spfa(int s)
{
    int head,tail,start,now,i;
    for (i=1;i<=n;i++)
    {
        dis[i]=0xfffffff;
        psum[i]=0;
        hash[i]=false;
    }
    head=tail=1;hash[s]=true;
    psum[s]=1;dis[s]=0;queue[1]=s;
    while (head<=tail)
    {
        start=queue[(head-1)%n+1];
        hash[start]=true;
        for (i=1;i<=l[start][0];i++)
        {
            now=l[start][i];
            if (dis[now]>dis[start]+cost[start][now])
            {
                dis[now]=dis[start]+cost[start][now];
                if (!hash[now])
                {
                    hash[now]=true;
                    tail++;
                    queue[(tail-1)%n+1]=now;
                    psum[now]++;
                    if (psum[now]>n)
                    {//記錄每個(gè)點(diǎn)進(jìn)隊(duì)的次數(shù)(判斷環(huán)的關(guān)鍵}
                        bk=false;
                        return;
                    }
                }
            }
        }
        head++;
        hash[start]=false;
        if (dis[s]<0)
        {//判斷環(huán)的一個(gè)優(yōu)化
            bk=false;
            return;
        }
    }
}
void output()
{
    bk=true;
    spfa(s);
    if (!bk)
    {
        printf("-1\n");
        return;
    }
    memcpy(a,dis,sizeof(long)*(n+1));
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff)
      {
            bk=true;
            spfa(i);
            if (!bk)
            {
                printf("-1\n");
                return;
            }
      }
    for (i=1;i<=n;i++)
      if (a[i]==0xfffffff) printf("NoPath\n");
      else printf("%d\n",a[i]);
}
void input()
{
    scanf("%d%d%d",&n,&m,&s);
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++)
        if (i==j) cost[i][j]=0;
        else cost[i][j]=0xfffffff;
    memset(l,0,sizeof(l));
    int x,y,c;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        if (c<cost[x][y])
        {
            cost[x][y]=c;
            l[x][0]++;
            l[x][l[x][0]]=y;
        }
    }
}
int main()
{
    input();
    output();
    system("pause");
    return 0;
}

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/bobcowwocb/archive/2009/09/14/4550188.aspx

2009年07月24日星期五 15:10

SPFA算法模版+鄰接表實(shí)現(xiàn)

SPFA即shotest path faster algorithm，由意思就可以看出該算法效率比較高。

其實(shí)SPFA就是bellman-ford算法的一個(gè)優(yōu)化。

具體做法是用一個(gè)隊(duì)列保存待松弛的點(diǎn)，然后對(duì)于每個(gè)出隊(duì)的點(diǎn)依次遍歷每個(gè)與他有邊相鄰的點(diǎn)（用鄰接表效率較高），如果該點(diǎn)可以松弛并且隊(duì)列中沒(méi)有該點(diǎn)則將它加入隊(duì)列中，如此迭代直到隊(duì)列為空。

據(jù)說(shuō)平均效率是O（E），可見(jiàn)對(duì)邊稀疏的圖用此算法效果是相當(dāng)可觀的。

若要判負(fù)環(huán)路,則記錄一個(gè)點(diǎn)的入隊(duì)次數(shù),若超過(guò)邊數(shù)，則有負(fù)權(quán)環(huán)。

#include <iostream>

#include <queue>

using namespace std;

const long MAXN=10000;

const long lmax=0x7FFFFFFF;

typedef struct

{

long v;

long next;

long cost;

}Edge;

Edge e[MAXN];

long p[MAXN];

long Dis[MAXN];

bool vist[MAXN];

queue<long> q;

long m,n;//點(diǎn),邊

void init()

{

long i;

long eid=0;

memset(vist,0,sizeof(vist));

memset(p,-1,sizeof(p));

fill(Dis,Dis+MAXN,lmax);

while (!q.empty())

{

q.pop();

}

for (i=0;i<n;++i)

{

long from,to,cost;

scanf("%ld %ld %ld",&from,&to,&cost);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

//以下適用于無(wú)向圖

swap(from,to);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

}

void print(long End)

{

//若為lmax 則不可達(dá)

printf("%ld\n",Dis[End]);

}

void SPF()

{

init();

long Start,End;

scanf("%ld %ld",&Start,&End);

Dis[Start]=0;

vist[Start]=true;

q.push(Start);

while (!q.empty())

{

long t=q.front();

q.pop();

vist[t]=false;

long j;

for (j=p[t];j!=-1;j=e[j].next)

{

long w=e[j].cost;

if (w+Dis[t]<Dis[e[j].v])

{

Dis[e[j].v]=w+Dis[t];

if (!vist[e[j].v])

{

vist[e[j].v]=true;

q.push(e[j].v);

}

print(End);

}

int main()

{

while (scanf("%ld %ld",&m,&n)!=EOF)

{

SPF();

}

return 0;

}

(請(qǐng)您對(duì)文章做出評(píng)價(jià))

一、Bellman-Ford算法

最優(yōu)性原理

它是最優(yōu)性原理的直接應(yīng)用，算法基于以下事實(shí)：

l 如果最短路存在，則每個(gè)頂點(diǎn)最多經(jīng)過(guò)一次，因此不超過(guò)n-1條邊；

l 長(zhǎng)度為k的路由長(zhǎng)度為k-1的路加一條邊得到；

l 由最優(yōu)性原理，只需依次考慮長(zhǎng)度為1，2，…，k-1的最短路。

適用條件&范圍

l 單源最短路徑(從源點(diǎn)s到其它所有頂點(diǎn)v);

l 有向圖&無(wú)向圖(無(wú)向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖);

l 邊權(quán)可正可負(fù)(如有負(fù)權(quán)回路輸出錯(cuò)誤提示);

l 差分約束系統(tǒng)（需要首先構(gòu)造約束圖，構(gòu)造不等式時(shí)>=表示求最小值, 作為最長(zhǎng)路，<=表示求最大值, 作為最短路。<=構(gòu)圖時(shí), 有負(fù)環(huán)說(shuō)明無(wú)解；求不出最短路（為Inf）為任意解。>=構(gòu)圖時(shí)類似）。

算法描述

l 對(duì)每條邊進(jìn)行|V|-1次Relax操作;

l 如果存在(u,v)∈E使得dis[u]+w<dis[v],則存在負(fù)權(quán)回路;否則dis[v]即為s到v的最短距離,pre[v]為前驅(qū)。

時(shí)空復(fù)雜度

for i:=1 to |V|-1 do

for 每條邊(u,v)∈E do Relax(u,v,w);

for每條邊(u,v)∈E do

if dis[u]+w<dis[v] Then Exit(False)

算法時(shí)間復(fù)雜度O(VE)。因?yàn)樗惴ê?jiǎn)單，適用范圍又廣，雖然復(fù)雜度稍高，仍不失為一個(gè)很實(shí)用的算法。

改進(jìn)和優(yōu)化如果循環(huán)n-1次以前已經(jīng)發(fā)現(xiàn)不存在緊邊則可以立即終止； Yen氏改進(jìn)（不降低漸進(jìn)復(fù)雜度）；SPFA算法

二、 SPFA算法

算法簡(jiǎn)介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。它可以在O(kE)的時(shí)間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。

算法流程
SPFA對(duì)Bellman-Ford算法優(yōu)化的關(guān)鍵之處在于意識(shí)到：只有那些在前一遍松弛中改變了距離估計(jì)值的點(diǎn)，才可能引起他們的鄰接點(diǎn)的距離估計(jì)值的改變。因此，算法大致流程是用一個(gè)隊(duì)列來(lái)進(jìn)行維護(hù)，即用一個(gè)先進(jìn)先出的隊(duì)列來(lái)存放被成功松弛的頂點(diǎn)。初始時(shí)，源點(diǎn)s入隊(duì)。當(dāng)隊(duì)列不為空時(shí)，取出隊(duì)首頂點(diǎn)，對(duì)它的鄰接點(diǎn)進(jìn)行松弛。如果某個(gè)鄰接點(diǎn)松弛成功，且該鄰接點(diǎn)不在隊(duì)列中，則將其入隊(duì)。經(jīng)過(guò)有限次的松弛操作后，隊(duì)列將為空，算法結(jié)束。SPFA算法的實(shí) 現(xiàn)，需要用到一個(gè)先進(jìn)先出的隊(duì)列 queue 和一個(gè)指示頂點(diǎn)是否在隊(duì)列中的標(biāo)記數(shù)組mark。為了方便查找某個(gè)頂點(diǎn)的鄰接點(diǎn)，圖采用臨界表存儲(chǔ)。

算法代碼
Procedure SPFA;Begin initialize-single-source(G,s); initialize-queue(Q); enqueue(Q,s); while not empty(Q) do begin u:=dequeue(Q); for each v∈adj[u] do begin tmp:=d[v]; relax(u,v); if (tmp<>d[v]) and (not v in Q) then enqueue(v); end; end;End;負(fù)環(huán)處理
需要特別注意的是：僅當(dāng)圖不存在負(fù)權(quán)回路時(shí)，SPFA能正常工作。如果圖存在負(fù)權(quán)回路，由于負(fù)權(quán)回路上的頂點(diǎn)無(wú)法收斂，總有頂點(diǎn)在入隊(duì)和出隊(duì)往返，隊(duì)列無(wú)法為空，這種情況下SPFA無(wú)法正常結(jié)束。

判斷負(fù)權(quán)回路的方案很多，世間流傳最廣、比較容易實(shí)現(xiàn)并且高效的方法的是記錄每個(gè)結(jié)點(diǎn)進(jìn)隊(duì)次數(shù)，超過(guò)|V|次表示有負(fù)權(quán)。

三、學(xué)以致用

POJ 1201 Intervals 差分約束系統(tǒng)

設(shè)S(i)為 0..i-1 中在最終序列中的的整數(shù)個(gè)數(shù)。則約束條件如下:

S(b)-S(a) >= c

0 <= S(i+1) - S(i) <= 1 <==> S(i+1)-S(i) >= 0;

S(i)-S(i+1) >= -1

注意本題要求的是最小值, 而按照>=號(hào)建圖后發(fā)現(xiàn)圖中有負(fù)環(huán), 怎么辦呢?

其實(shí)很簡(jiǎn)單, 本題求的不是最短路, 而是最長(zhǎng)路! Bellman_ford即可!

POJ 1275 Cashier Employment 出納員的雇傭

黑書(shū)上有詳細(xì)講解

POJ 1364 King 差分約束系統(tǒng)

這個(gè)題目構(gòu)圖之后, 只需要用bellman_ford判斷是否有負(fù)圈.

構(gòu)圖方法:

首先進(jìn)行轉(zhuǎn)換:a[j]+...+a[j+m] = a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -

sum[j-1] >(<) ki. 差分約束只能全部是<=或者(>=).

第二步轉(zhuǎn)換: sum[j+m]-sum[j-1] <= ki-1 或者 sum[j-1]-sum[j+m] <= -ki-1.

約束圖構(gòu)造好后就是簡(jiǎn)單的Bellman-Ford了!

POJ 1716 Integer Intervals 是1201的簡(jiǎn)單版本, 貪心算法能夠得到更好的效果.

POJ 2983 Is the Information Reliable?

差分約束題, 處理一下等號(hào)的情況, 然后普通的Bellman_ford

POJ 3159 Candies 最短路徑

Bellman-Ford超時(shí), Dijkstra算法可以高效解決, SPFA(隊(duì)列)居然超時(shí)...SPFA修改為堆棧實(shí)現(xiàn)就過(guò)了.

POJ 3169 Layout 差分約束

Bellman-Ford 和 SPFA 實(shí)現(xiàn)均可

POJ 3259 Wormholes 判斷負(fù)權(quán)回路

TOJ 2976 Path 單純的最短路徑可練習(xí)SPFA

ZOJ 3033 Board Games 我做的第一道Bellman-Ford題目

首先，DFS判斷可達(dá)性，不可達(dá)直接輸出infinity結(jié)束，可達(dá)，bellman-ford判斷是否存在負(fù)環(huán)，存在輸出infinity，否則，輸出最短距離。

SPFA算法模版+鄰接表實(shí)現(xiàn)

SPFA即shotest path faster algorithm，由意思就可以看出該算法效率比較高。

其實(shí)SPFA就是bellman-ford算法的一個(gè)優(yōu)化。

據(jù)說(shuō)平均效率是O（E），可見(jiàn)對(duì)邊稀疏的圖用此算法效果是相當(dāng)可觀的。

若要判負(fù)環(huán)路,則記錄一個(gè)點(diǎn)的入隊(duì)次數(shù),若超過(guò)邊數(shù)，則有負(fù)權(quán)環(huán)。

#include <iostream>

#include <queue>

using namespace std;

const long MAXN=10000;

const long lmax=0x7FFFFFFF;

typedef struct

{

long v;

long next;

long cost;

}Edge;

Edge e[MAXN];

long p[MAXN];

long Dis[MAXN];

bool vist[MAXN];

queue<long> q;

long m,n;//點(diǎn),邊

void init()

{

long i;

long eid=0;

memset(vist,0,sizeof(vist));

memset(p,-1,sizeof(p));

fill(Dis,Dis+MAXN,lmax);

while (!q.empty())

{

q.pop();

}

for (i=0;i<n;++i)

{

long from,to,cost;

scanf("%ld %ld %ld",&from,&to,&cost);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

//以下適用于無(wú)向圖

swap(from,to);

e[eid].next=p[from];

e[eid].v=to;

e[eid].cost=cost;

p[from]=eid++;

}

void print(long End)

{

//若為lmax 則不可達(dá)

printf("%ld\n",Dis[End]);

}

void SPF()

{

init();

long Start,End;

scanf("%ld %ld",&Start,&End);

Dis[Start]=0;

vist[Start]=true;

q.push(Start);

while (!q.empty())

{

long t=q.front();

q.pop();

vist[t]=false;

long j;

for (j=p[t];j!=-1;j=e[j].next)

{

long w=e[j].cost;

if (w+Dis[t]<Dis[e[j].v])

{

Dis[e[j].v]=w+Dis[t];

if (!vist[e[j].v])

{

vist[e[j].v]=true;

q.push(e[j].v);

}

print(End);

}

int main()

{

while (scanf("%ld %ld",&m,&n)!=EOF)

{

SPF();

}

return 0;

}

POJ 1511-Invitation Cards(SPFA算法)

今天終于用SPFA寫(xiě)出了第一個(gè)程序，感覺(jué)收獲很大，從Dij到Floyed再到Bellmen，以及今天的SPFA，每一種算法背后都蘊(yùn)藏著許多值得思考的地方。正因?yàn)檠芯苛怂鼈儯攀沟梦业哪芰Σ粩嗟孬@得了提高。
之前以為SPFA做為最短路問(wèn)題最快的算法，想必代碼定不好寫(xiě)，不過(guò)今天研究過(guò)才知道，SPFA的代碼量遠(yuǎn)遠(yuǎn)不及Dij，這著實(shí)令人驚嘆，原來(lái)最好的算法SPFA是如此的好寫(xiě)，呵呵我想此算法在很大程度上可以完全代替之前的算法，以后再碰到最短路問(wèn)題時(shí)，SPFA一定能成為首要的選擇！
PS:由于是用鄰接表來(lái)存儲(chǔ)的，所以每次操作前要收回以前分配的內(nèi)存，我嘗試了收回和不收回兩種方法，發(fā)現(xiàn)其實(shí)差別不大，如果純粹是比賽的話，可能不收回反而會(huì)更好些（避免超時(shí)）。當(dāng)然如果在實(shí)際應(yīng)用中，應(yīng)該切記內(nèi)存的分配，否則軟件可能會(huì)發(fā)生異常。

//Coded by abilitytao

//Time:2009-04-10 22:49:58

#include<iostream>

#include<cmath>

#include<queue>

using namespace std;

#define MAX_NUM 1000000001

#define MAX_DOTNUM 1000001

int n,m;

queue<int>myqueue;

bool mark[MAX_DOTNUM];

__int64 dis[MAX_DOTNUM];

struct node

{

int v;

int w;

node *next;

}edge[MAX_DOTNUM];//此鄰接表用于存儲(chǔ)正向圖

node reversed_edge[MAX_DOTNUM];//此逆鄰接表用于存儲(chǔ)逆向圖

void initial(node edge[])//鄰接表的初始化，里面封裝了回收上一次操作所分配之內(nèi)存的操作

{

int i;

node *p;

node *q;

for(i=1;i<=n;i++)

{

p=&edge[i];

q=p->next;

while(q!=NULL)

{

p->next=q->next;

delete q;

q=p->next;

}

void input_case()//每一個(gè)case的輸入函數(shù)

{

int i;

for(i=1;i<=m;i++)

{

node *p;

node *q;

int a,b,c;

scanf("%d%d%d",&a,&b,&c);

////////////////////////

p=&edge[a];

q=new node;

q->v=b;

q->w=c;

q->next=p->next;

p->next=q;

////////////////////////

p=&reversed_edge[b];

q=new node;

q->v=a;

q->w=c;

q->next=p->next;

p->next=q;

}

void spfa(node edge[])//SPFA部分

{

int i;

///////////////////////////////////////////////////////////////

memset(mark,false,sizeof(mark));

for(i=1;i<=n;i++)

dis[i]=MAX_NUM;

while(myqueue.size()!=0)

myqueue.pop();

///////////////////////////////////////////////////////////

dis[1]=0;

mark[1]=true;

myqueue.push(1);

while(myqueue.size()!=0)//如果隊(duì)列不空，則進(jìn)行松弛操作，直到隊(duì)列空為止

{

int temp=myqueue.front();

myqueue.pop();

mark[temp]=false;

node *p;

for(p=edge[temp].next;p!=NULL;p=p->next)

{

if(dis[p->v]>dis[temp]+p->w)

{

dis[p->v]=dis[temp]+p->w;

if(mark[p->v]!=true)

{

myqueue.push(p->v);

mark[p->v]=true;

}

int main()

{

int testcase;

int i,j;

__int64 sum;

scanf("%d",&testcase);

for(i=1;i<=MAX_DOTNUM-1;i++)

{

edge[i].v=i;

edge[i].w=0;

edge[i].next=NULL;

}

for(i=1;i<=MAX_DOTNUM-1;i++)

{

reversed_edge[i].v=i;

reversed_edge[i].w=0;

reversed_edge[i].next=NULL;

}

for(i=1;i<=testcase;i++)

{

sum=0;

scanf("%d%d",&n,&m);

initial(edge);

initial(reversed_edge);

input_case();

spfa(edge);

for(j=1;j<=n;j++)

sum+=dis[j];

spfa(reversed_edge);

for(j=1;j<=n;j++)

sum+=dis[j];

printf("%I64d\n",sum);

}

system("pause");

return 0;

}

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問(wèn) 管理
相關(guān)文章: AC算法使用例子使用用最小堆來(lái)找最大的K個(gè)數(shù) zz求二叉樹(shù)中節(jié)點(diǎn)的最大距離 zz精華游戲算法整理 pku3233　矩陣相乘的反復(fù)平方法和矩陣等比和計(jì)算構(gòu)造方法最小表示法排序算法、時(shí)間復(fù)雜度與信息熵 zz 傳說(shuō)中效率最高的最大流算法(Dinic) zz 最短路徑之 SPFA算法 zz C語(yǔ)言編一個(gè)簡(jiǎn)單的計(jì)算器

與心靈對(duì)話

導(dǎo)航

常用鏈接

留言簿(14)

隨筆分類

隨筆檔案

文章檔案

相冊(cè)

收藏夾

技術(shù)基礎(chǔ)

技術(shù)相關(guān)

研究方向

算法類

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

最短路徑之 SPFA算法 zz

SPFA算法模版+鄰接表實(shí)現(xiàn)

SPFA算法模版+鄰接表實(shí)現(xiàn)

與心靈對(duì)話

導(dǎo)航

常用鏈接

留言簿(14)

隨筆分類

隨筆檔案

文章檔案

相冊(cè)

收藏夾

技術(shù)基礎(chǔ)

技術(shù)相關(guān)

研究方向

算法類

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

最短路徑 之 SPFA算法 zz

SPFA算法模版+鄰接表實(shí)現(xiàn)

SPFA算法模版+鄰接表實(shí)現(xiàn)

最短路徑之 SPFA算法 zz