SPFA

SPFA模版

单源：假设1为起点，适合于稀疏图，O（边数）

         

queue<int> q;
while(!q.empty())
{
    int now=q.front();
    q.pop();
    for(int e=head[now];e!=-1;e=map[e].next)
    {
         if(dis[map[e].y]==-1)//没进过队
         {
              /*1*/q.push(map[e].y);
              /*2*/dis[map[e].y]=dis[now]+1;
          }
     }
}

BFS求一个问题入队一次

while(!e.empty())
{
    int now=q.front(),q.pop();
    for()//省略
    {
         flag[now]=0;
         if(dis[now]+map[e].w<dis[map[e.y]])
         {
             dis[map[e].y]=map[e].w+dis[now];
             if(flag[map[e].y]==0)
             {
                 q.push(map[e].y);
                 flag[map[e].y]=1;
             }
         }
    }
}

　　

SPFA入队多次，更加适合求两点之间的最短路，空间少，时间也少，但是如果求多源最短路还是建议大家用Floyd算法