最短路（SPFA算法）讲解+例题

SPFA 算法介绍

SPFA 算法是 Bellman-Ford算法的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

算法的思路：

（转自https://blog.csdn.net/qq_35644234/article/details/61614581）

    我们用数组dis记录每个结点的最短路径估计值，用  邻接表 或  邻接矩阵 来存储图G。我们采取的方法是动态逼近法：

    设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止

我们要知道带有负环的图是没有最短路径的，所以我们在执行算法的时候，要判断图是否带有负环，方法有两种：

1. 开始算法前，调用拓扑排序进行判断（一般不采用，浪费时间）
2. 如果某个点进入队列的次数超过N次则存在负环（N为图的顶点数）

SPFA算法手动操作过程

（转自https://blog.csdn.net/qq_35644234/article/details/61614581）

下面我们采用SPFA算法对下图求v1到各个顶点的最短路径，通过手动的方式来模拟SPFA每个步骤的过程

• 初始化：

首先我们先初始化数组dis如下图所示：（除了起点赋值为0外，其他顶点的对应的dis的值都赋予无穷大，这样有利于后续的松弛） 

此时，我们还要把v1如队列：{v1}

现在进入循环，直到队列为空才退出循环。

• 第一次循环：

首先，队首元素出队列，即是v1出队列，然后，对以v1为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v3，v5，v6三个顶点的最短路径变短了，更新dis数组的值，得到如下结果： 

我们发现v3，v5，v6都被松弛了，而且不在队列中，所以要他们都加入到队列中：{v3，v5，v6}

• 第二次循环

此时，队首元素为v3，v3出队列，然后，对以v3为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v4的边，经过v3松弛变短了，所以更新dis数组，得到如下结果： 

此时只有v4对应的值被更新了，而且v4不在队列中，则把它加入到队列中：{v5,v6,v4}

• 第三次循环

此时，队首元素为v5，v5出队列，然后，对以v5为弧尾的边对应的弧头顶点进行松弛操作，发现v1到v4和v6的最短路径，经过v5的松弛都变短了，更新dis的数组，得到如下结果： 

我们发现v4、v6对应的值都被更新了，但是他们都在队列中了，所以不用对队列做任何操作。队列值为：{v6，v4}

• 第四次循环 
  此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作，它的值为：{v4}

• 第五次循环 
  此时，队首元素为v4，v4出队列，然后，对以v4为弧尾的边对应的弧头顶点进行松弛操作，可以发现v1到v6的最短路径，经过v4松弛变短了，所以更新dis数组，得到如下结果： 
  

因为我修改了v6对应的值，而且v6也不在队列中，所以我们把v6加入队列，{v6}

• 第六次循环 
  此时，队首元素为v6，v6出队列，然后，对以v6为弧尾的边对应的弧头顶点进行松弛操作，发现v6出度为0，所以我们不用对dis数组做任何操作，其结果和上图一样，队列同样不用做任何操作。所以此时队列为空。

OK，队列循环结果，此时我们也得到了v1到各个顶点的最短路径的值了，它就是dis数组各个顶点对应的值，如下图： 

例题 

POJ

2394

Checking an Alibi

题目链接

http://poj.org/problem?id=2394

题目

Checking an Alibi

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7303		Accepted: 2685

Description

A crime has been comitted: a load of grain has been taken from the barn by one of FJ's cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. 

Farmer John's farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). 

Given the layout of Farmer John's farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. 

NOTE: Do not declare a variable named exactly 'time'. This will reference the system call and never give you the results you really want.

Input

* Line 1: Four space-separated integers: F, P, C, and M 

* Lines 2..P+1: Three space-separated integers describing a path: F1,F2, and T. The path connects F1 and F2 and requires T seconds to traverse. 

* Lines P+2..P+C+1: One integer per line, the location of a cow. The first line gives the field number of cow 1, the second of cow 2, etc.

Output

* Line 1: A single integer N, the number of cows that could be guilty of the crime. 

* Lines 2..N+1: A single cow number on each line that is one of the cows that could be guilty of the crime. The list must be in ascending order.

Sample Input

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

Sample Output

4
1
2
3
4

Hint

INPUT DETAILS: 

Fields/distances like this: 

          6

      4------5

      |      |

     2|      |

      |      |

7-----1      |5

   9  |      |

     1|      |

      |      |

      2------3

OUTPUT DETAILS: 

Any cow except cow 5 could have done it. Cow 5 would take 9 seconds to get to the barn.

题意：

给出路径和牛的位置 要求求每只牛到粮仓的最短距离  如果距离小于等于m 则 sum++ 最后把小于m的牛的编号按升序输出

AC代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f3f;
int a,b,w,f,p,c,m,allroad,vis[100000],head[100000],dis[100000],ox[100000],sum;
struct r
{
    int e,d,nextroad;
}road[100000];
void add(int a,int b,int w)
{
    road[allroad].e = b;
    road[allroad].d = w;
    road[allroad].nextroad = head[a];
    head[a] = allroad;
}
void SPFA()
{
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=f; i++)
        if(i==1)dis[i]=0;
        else dis[i]=inf;
    queue <int> q;
    while(!q.empty())q.pop();
    q.push(1);
    vis[1] = 1;
    while(!q.empty())
    {
        int now = q.front();
        q.pop();vis[now]=0;
        for(int i=head[now];i!=-1;i=road[i].nextroad)
        {
            int to=road[i].e;
            int dd=road[i].d;
            if((dis[now]+dd)<dis[to])
            {
                dis[to] = dis[now]+dd;
                if(vis[to]==0)
                {
                    q.push(to);
                    vis[to] = 1;
                }
            }
        }
    }
}
int main()
{
    while(scanf("%d%d%d%d",&f,&p,&c,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        allroad = 0;
        for(int i=0;i<p;i++)
        {
            scanf("%d%d%d",&a,&b,&w);
            add(a,b,w); allroad++;
            add(b,a,w); allroad++;
        }
        for(int i=1;i<=c;i++)
            scanf("%d",&ox[i]);
        SPFA();
    }
    sum=0;
    queue <int> p;
    while(!p.empty())p.pop();
    for(int i=1;i<=c;i++)
    {
        int x=ox[i];
        if(dis[x]<=m){sum++;p.push(i);}
    }
    printf("%d\n",sum);
    while(!p.empty())
    {
        printf("%d\n",p.front());
        p.pop();
    }
    return 0;
}