SPFA算法

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

C语言描述

以下描述中，start为源，dist存源到所有点的最短路长度，Connect[]、Pre[]、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);
 }