SPFA即shotest path faster algorithm，由意思就可以看出該算法效率比較高。
其實(shí)SPFA就是bellman-ford算法的一個優(yōu)化。
具體做法是用一個隊列保存待松弛的點(diǎn)，然后對于每個出隊的點(diǎn)依次遍歷每個與他有邊相鄰的點(diǎn)（用鄰接表效率較高），如果該點(diǎn)可以松弛并且隊列中沒有該點(diǎn)則將它加入隊列中，如此迭代直到隊列為空。
據(jù)說平均效率是O（E），可見對邊稀疏的圖用此算法效果是相當(dāng)可觀的。
若要判負(fù)環(huán)路,則記錄一個點(diǎn)的入隊次數(shù),若超過邊數(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++;
//以下適用于無向圖
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;
}