SPFA算法

SPFA算法（Shortest Path Faster Algorithm）是一種單源最短路算法。因為其算法速度快，代碼簡單，並可以計算負權，所以SPFA算法在信息學競賽領域已經逐漸替代其他單源最短路算法。SPFA本质上是Bellman-Ford算法的优化。

C语言描述

以下描述中，start为源，dist存源到所有点的最短路长度，Connect[]、Data[]为数组实现的临接表。

void spfa(int start){
 int i,j;
 //初始化部分
 for (i=1;i<=n;++i){
   dist[i]=2147483647;
   inqueue[i]=0;
 }           
 dist[start]=0;
 int h=0,t=1;
 inqueue[start]=1;
 queue[1]=start;
 int now;
 do{
   h++;
   now=Connect[queue[h]];
   inqueue[queue[h]]=0;
   while (now){
     if (dist[Data[now].v]>dist[queue[h]]+Data[now].w){
       dist[Data[now].v]=dist[queue[h]]+Data[now].w;
       if (!inqueue[Data[now].v]){
         inqueue[Data[now].v]=1;
         queue[++t]=Data[now].v;
       }
     }
     now=Pre[now];
   }
 }while (h<t);
}