SPFA 算法詳解( 強(qiáng)大圖解，不會都難！)

Rainboy913 2013-12-08

展開全文

適用范圍：給定的圖存在負(fù)權(quán)邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復(fù)雜度又過高，SPFA算法便派上用場了。我們約定有向加權(quán)圖G不存在負(fù)權(quán)回路，即最短路徑一定存在。當(dāng)然，我們可以在執(zhí)行該算法前做一次拓?fù)渑判?，以判斷是否存在?fù)權(quán)回路，但這不是我們討論的重點(diǎn)。

算法思想：我們用數(shù)組d記錄每個結(jié)點(diǎn)的最短路徑估計(jì)值，用鄰接表來存儲圖G。我們采取的方法是動態(tài)逼近法：設(shè)立一個先進(jìn)先出的隊(duì)列用來保存待優(yōu)化的結(jié)點(diǎn)，優(yōu)化時每次取出隊(duì)首結(jié)點(diǎn)u，并且用u點(diǎn)當(dāng)前的最短路徑估計(jì)值對離開u點(diǎn)所指向的結(jié)點(diǎn)v進(jìn)行松弛操作，如果v點(diǎn)的最短路徑估計(jì)值有所調(diào)整，且v點(diǎn)不在當(dāng)前的隊(duì)列中，就將v點(diǎn)放入隊(duì)尾。這樣不斷從隊(duì)列中取出結(jié)點(diǎn)來進(jìn)行松弛操作，直至隊(duì)列空為止

期望的時間復(fù)雜度O(ke)，其中k為所有頂點(diǎn)進(jìn)隊(duì)的平均次數(shù)，可以證明k一般小于等于2。

實(shí)現(xiàn)方法：

　　建立一個隊(duì)列，初始時隊(duì)列里只有起始點(diǎn)，再建立一個表格記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值，該點(diǎn)到他本身的路徑賦為0）。然后執(zhí)行松弛操作，用隊(duì)列里有的點(diǎn)作為起始點(diǎn)去刷新到所有點(diǎn)的最短路，如果刷新成功且被刷新點(diǎn)不在隊(duì)列中則把該點(diǎn)加入到隊(duì)列最后。重復(fù)執(zhí)行直到隊(duì)列為空。

判斷有無負(fù)環(huán)：
　　如果某個點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過N次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）

首先建立起始點(diǎn)a到其余各點(diǎn)的
最短路徑表格

首先源點(diǎn)a入隊(duì)，當(dāng)隊(duì)列非空時：
　１、隊(duì)首元素（a）出隊(duì)，對以a為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有b,c,d三個點(diǎn)），此時路徑表格狀態(tài)為：

在松弛時三個點(diǎn)的最短路徑估值變小了，而這些點(diǎn)隊(duì)列中都沒有出現(xiàn)，這些點(diǎn)
需要入隊(duì)，此時，隊(duì)列中新入隊(duì)了三個結(jié)點(diǎn)b,c,d

隊(duì)首元素b點(diǎn)出隊(duì)，對以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e的最短路徑估值也變小了，e在隊(duì)列中不存在，因此e也要
入隊(duì)，此時隊(duì)列中的元素為c，d，e

隊(duì)首元素c點(diǎn)出隊(duì)，對以c為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有e,f兩個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e，f的最短路徑估值變小了，e在隊(duì)列中存在，f不存在。因此
e不用入隊(duì)了，f要入隊(duì)，此時隊(duì)列中的元素為d，e，f

隊(duì)首元素d點(diǎn)出隊(duì)，對以d為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，g的最短路徑估值沒有變?。ㄋ沙诓怀晒Γ?，沒有新結(jié)點(diǎn)入隊(duì)，隊(duì)列中元素為f，g

隊(duì)首元素f點(diǎn)出隊(duì)，對以f為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處有d，e，g三個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e，g的最短路徑估值又變小，隊(duì)列中無e點(diǎn)，e入隊(duì)，隊(duì)列中存在g這個點(diǎn)，g不用入隊(duì)，此時隊(duì)列中元素為g，e

隊(duì)首元素g點(diǎn)出隊(duì)，對以g為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有b點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，b的最短路徑估值又變小，隊(duì)列中無b點(diǎn)，b入隊(duì)，此時隊(duì)列中元素為e，b
隊(duì)首元素e點(diǎn)出隊(duì)，對以e為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有g(shù)這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，g的最短路徑估值沒變化（松弛不成功），此時隊(duì)列中元素為b

隊(duì)首元素b點(diǎn)出隊(duì)，對以b為起始點(diǎn)的所有邊的終點(diǎn)依次進(jìn)行松弛操作（此處只有e這個點(diǎn)），此時路徑表格狀態(tài)為：

在最短路徑表中，e的最短路徑估值沒變化（松弛不成功），此時隊(duì)列為空了

最終a到g的最短路徑為１４

program：

#include<cstdio>
using namespace std;
struct node
{int x;
int value;
int next;
};
node e[60000];
int visited[1505],dis[1505],st[1505],queue[1000];
int main()
{
int n,m,u,v,w,start,h,r,cur;
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
    for(int i=1;i<=1500;i++)
      {visited[i]=0;
       dis[i]=-1;
       st[i]=-1; //這個初始化給下邊那個while循環(huán)帶來影響
      }

   for(int i=1;i<=m;i++)
      {
       scanf("%d%d%d\n",&u,&v,&w);
       e[i].x=v;            //記錄后繼節(jié)點(diǎn)    相當(dāng)于鏈表中的創(chuàng)建一個節(jié)點(diǎn)，并使得數(shù)據(jù)域先記錄
       e[i].value=w;
       e[i].next=st[u];     //記錄頂點(diǎn)節(jié)點(diǎn)的某一個邊表節(jié)點(diǎn)的下標(biāo)，相當(dāng)于在鏈表中吧該邊表節(jié)點(diǎn)的next指針先指向他的后繼邊表節(jié)點(diǎn)
       st[u]=i;                //把該頂點(diǎn)的指針指向邊表節(jié)點(diǎn)，相當(dāng)于鏈表中的插入中，頭結(jié)點(diǎn)的指針改變
      }
    start=1;
    visited[start]=1;
    dis[start]=0;
    h=0;
    r=1;
    queue[r]=start;
    while(h!=r)
     {

      h=(h+1)%1000;
      cur=queue[h];
      int tmp=st[cur];
      visited[cur]=0;

     while(tmp!=-1)
        {
           if (dis[e[tmp].x]<dis[cur]+e[tmp].value)            //改成大于號才對
           {
                   dis[e[tmp].x]=dis[cur]+e[tmp].value;
                  if(visited[e[tmp].x]==0)
                      {

                          visited[e[tmp].x]=1;
                          r=(r+1)%1000;
                            queue[r]=e[tmp].x;
                      }
          }
         tmp=e[tmp].next;
        }
     }
    printf("%d\n",dis[n]);
}
return 0;
}

(沒有質(zhì)量，就出數(shù)量) 下面一文轉(zhuǎn)載出處：http://blog.csdn.net/morgan_xww/article/details/6279596

/*
SPFA(Shortest Path Faster Algorithm) [圖的存儲方式為鄰接表]
是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。
算法大致流程是用一個隊(duì)列來進(jìn)行維護(hù)。初始時將源加入隊(duì)列。每次從隊(duì)列中取出一個元素，
并對所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個相鄰的點(diǎn)松弛成功，則將其入隊(duì)。直到隊(duì)列為空時算法結(jié)束。
它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。
SPFA 在形式上和BFS非常類似，不同的是BFS中一個點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中
一個點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時間可能本
身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。
判斷有無負(fù)環(huán)：如果某個點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過V次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）。
SPFA算法有兩個優(yōu)化算法 SLF 和 LLL：
SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)<dist(i)，則將j插入隊(duì)首，
否則插入隊(duì)尾。
LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i，隊(duì)列中所有dist值的平均值為x，若dist(i)>x則將i插入
到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對進(jìn)行松弛操作。
引用網(wǎng)上資料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。
在實(shí)際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。
*/
//用數(shù)組實(shí)現(xiàn)鄰接表存儲，pnt[i,0]表示與i相鄰的結(jié)點(diǎn)個數(shù)，pnt[i,1...k]存儲與i相鄰的點(diǎn)
int pnt[MAXN][MAXN];
int map[MAXN][MAXN]; //map[i,j]為初始輸入的i到j(luò)的距離，并且map[i,i]=0;未知的map[i,j]=INF;
int dis[MAXN];
char vst[MAXN];
int SPFA(int n,int s)
{
int i, pri, end, p, t;
memset(vst, 0, sizeof(vst));
for (i=1; i<=n; i++)
dis[i] = INF;
dis[s] = 0;
vst[s] = 1;
Q[0] = s; pri = 0; end = 1;
while (pri < end)
{
p = Q[pri];
for (i=1; i<=pnt[p][0]; i++)
{
t = pnt[p][i];
//先釋放，釋放成功后再判斷是否要加入隊(duì)列
if (dis[p]+map[p][t] < dis[t])
{
dis[t] = dis[p]+map[p][t];
if (!vst[t])
{
Q[end++] = t;
vst[t] = 1;
}
}
}
vst[p] = 0;
pri++;
}
return 1;
}

/*
SPFA(Shortest Path Faster Algorithm) [圖的存儲方式為鄰接表]
是Bellman-Ford算法的一種隊(duì)列實(shí)現(xiàn)，減少了不必要的冗余計(jì)算。
算法大致流程是用一個隊(duì)列來進(jìn)行維護(hù)。初始時將源加入隊(duì)列。每次從隊(duì)列中取出一個元素，
并對所有與他相鄰的點(diǎn)進(jìn)行松弛，若某個相鄰的點(diǎn)松弛成功，則將其入隊(duì)。直到隊(duì)列為空時算法結(jié)束。
它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點(diǎn)到其他所有點(diǎn)的最短路徑，可以處理負(fù)邊。
SPFA 在形式上和BFS非常類似，不同的是BFS中一個點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中
一個點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時間可能本
身被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。
判斷有無負(fù)環(huán)：如果某個點(diǎn)進(jìn)入隊(duì)列的次數(shù)超過V次則存在負(fù)環(huán)（SPFA無法處理帶負(fù)環(huán)的圖）。
SPFA算法有兩個優(yōu)化算法 SLF 和 LLL：
SLF：Small Label First 策略，設(shè)要加入的節(jié)點(diǎn)是j，隊(duì)首元素為i，若dist(j)<dist(i)，則將j插入隊(duì)首，
否則插入隊(duì)尾。
LLL：Large Label Last 策略，設(shè)隊(duì)首元素為i，隊(duì)列中所有dist值的平均值為x，若dist(i)>x則將i插入
到隊(duì)尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出對進(jìn)行松弛操作。
引用網(wǎng)上資料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。
在實(shí)際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。
*/
//用數(shù)組實(shí)現(xiàn)鄰接表存儲，pnt[i,0]表示與i相鄰的結(jié)點(diǎn)個數(shù)，pnt[i,1...k]存儲與i相鄰的點(diǎn)
int pnt[MAXN][MAXN];
int map[MAXN][MAXN]; //map[i,j]為初始輸入的i到j(luò)的距離，并且map[i,i]=0;未知的map[i,j]=INF;
int dis[MAXN];
char vst[MAXN];
int SPFA(int n, int s)
{
int i, pri, end, p, t;
memset(vst, 0, sizeof(vst));
for (i=1; i<=n; i++)
dis[i] = INF;
dis[s] = 0;
vst[s] = 1;
Q[0] = s; pri = 0; end = 1;
while (pri < end)
{
p = Q[pri];
for (i=1; i<=pnt[p][0]; i++)
{
t = pnt[p][i];
//先釋放，釋放成功后再判斷是否要加入隊(duì)列
if (dis[p]+map[p][t] < dis[t])
{
dis[t] = dis[p]+map[p][t];
if (!vst[t])
{
Q[end++] = t;
vst[t] = 1;
}
}
}
vst[p] = 0;
pri++;
}
return 1;
}

正規(guī)鄰接表存儲：
/* ------- 鄰接表存儲 ----------- */
struct Edge
{
int e; //終點(diǎn)
int v; //邊權(quán)
struct Edge *nxt;
};
struct
{
struct Edge *head, *last;
} node[MAXN];
/* -------------------------------- */
/* 添加有向邊<起點(diǎn),終點(diǎn),邊權(quán)> */
void add(int s,int e,int v)
{
struct Edge *p;
p = (struct Edge*)malloc(sizeof(struct Edge));
p->e = e;
p->v = v;
p->nxt = NULL;
if (node[s].head == NULL)
{
node[s].head = p;
node[s].last = p;
}
else
{
node[s].last->nxt = p;
node[s].last = p;
}
}
/* 松弛，成功返回1，否則0 */
int relax(int s,int e,int v)
{
if (dis[s]+v < dis[e])
{
dis[e] = dis[s]+v;
return 1;
}
return 0;
}
/* SPFA有負(fù)權(quán)回路返回0,否則返回1并且最短路徑保存在dis[] */
int n;
int vst[MAXN], cnt[MAXN];
int Q[MAXN*MAXN];
int SPFA(int s0)
{
int i, p, q;
struct Edge *pp;
memset(vst, 0, sizeof(vst));
memset(cnt, 0, sizeof(cnt));
for (i=0; i<=n; i++)
dis[i] = INF;
dis[s0] = 0;
Q[0] = s0; p = 0; q = 1;
vst[s0] = 1;
cnt[s0]++;
while (p < q)
{
pp = node[Q[p]].head;
while (pp)
{
if (relax(Q[p], pp->e, pp->v) && !vst[pp->e])
{
Q[q++] = pp->e;
vst[pp->e] = 1;
cnt[pp->e]++;
if (cnt[pp->e] > n) //有負(fù)權(quán)回路
return 0;
}
pp = pp->nxt;
}
vst[Q[p]] = 0;
p++;
}
return 1;
}

正規(guī)鄰接表存儲：
/* ------- 鄰接表存儲 ----------- */
struct Edge
{
int e; //終點(diǎn)
int v; //邊權(quán)
struct Edge *nxt;
};
struct
{
struct Edge *head, *last;
} node[MAXN];
/* -------------------------------- */
/* 添加有向邊<起點(diǎn),終點(diǎn),邊權(quán)> */
void add(int s, int e, int v)
{
struct Edge *p;
p = (struct Edge*)malloc(sizeof(struct Edge));
p->e = e;
p->v = v;
p->nxt = NULL;
if (node[s].head == NULL)
{
node[s].head = p;
node[s].last = p;
}
else
{
node[s].last->nxt = p;
node[s].last = p;
}
}
/* 松弛，成功返回1，否則0 */
int relax(int s, int e, int v)
{
if (dis[s]+v < dis[e])
{
dis[e] = dis[s]+v;
return 1;
}
return 0;
}
/* SPFA有負(fù)權(quán)回路返回0,否則返回1并且最短路徑保存在dis[] */
int n;
int vst[MAXN], cnt[MAXN];
int Q[MAXN*MAXN];
int SPFA(int s0)
{
int i, p, q;
struct Edge *pp;
memset(vst, 0, sizeof(vst));
memset(cnt, 0, sizeof(cnt));
for (i=0; i<=n; i++)
dis[i] = INF;
dis[s0] = 0;
Q[0] = s0; p = 0; q = 1;
vst[s0] = 1;
cnt[s0]++;
while (p < q)
{
pp = node[Q[p]].head;
while (pp)
{
if (relax(Q[p], pp->e, pp->v) && !vst[pp->e])
{
Q[q++] = pp->e;
vst[pp->e] = 1;
cnt[pp->e]++;
if (cnt[pp->e] > n) //有負(fù)權(quán)回路
return 0;
}
pp = pp->nxt;
}
vst[Q[p]] = 0;
p++;
}
return 1;
}

/**通過poj 3159 證明：還是用數(shù)組來實(shí)現(xiàn)鄰接表比用鏈表來實(shí)現(xiàn)鄰接表效率高， **/
#define MAX_node 10000
#define MAX_edge 100000
struct Edge
{
int e, v;
} edge[MAX_edge];
int neg; //number of edge
int node[MAX_node]; //注意node要用memset初始化全部為-1
int next[MAX_edge];
void add(int s,int e,int v)
{
edge[neg].e = e;
edge[neg].v = v;
next[neg] = node[s];
node[s] = neg++;
}
/* 該題還證明用棧來實(shí)現(xiàn)SPFA比用隊(duì)列來實(shí)現(xiàn)效率高，還節(jié)約空間 */
int SPFA(int s0)//棧實(shí)現(xiàn)
{
int i, t, p, top;
memset(vst, 0, sizeof(vst));
for (i=1; i<=n; i++)
dis[i] = INF;
dis[s0] = 0;
Q[0] = s0;
top = 1;
vst[s0] = 1;
while (top)
{
t = Q[--top];
vst[t] = 0;
p = node[t];
while (p != -1)
{
if (relax(t, edge[p].e, edge[p].v) && !vst[edge[p].e])
{
Q[top++] = edge[p].e;
vst[edge[p].e] = 1;
}
p = next[p];
}
}
return 1;
}

本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： Rainboy913 > 《SPFA 算法》

舉報(bào)/認(rèn)領(lǐng)