最短路径----spfa

单源最短路径

思路:

spfa算法是bellman_ford的队列优化算法，bellman是枚举所有的边，所以其时间复杂度为O(nm)，而spfa则是只枚举之前改变了值的边，如果当前点被改变了值，则讲这个点放到队列当中去，如果已经在队列当中了，就不需要再次放入队列当中，然后每次取出队列头部的点，再反复操作，整个图没有点被更新，也就是队列为空的时候。

时间复杂度O(km)(k为常数 m为边数)

Code：

#include<iostream>
#include<queue>
#include<memory.h>
#include<cmath>
using namespace std;
const int N=500005;
int head[N],ver[N],edge[N],ne[N];//邻接表存图
int tot,d[N],v[N];
int n,m,s;
void add(int x,int y,int z)
{
    ver[++tot]=y;//存放终点
    edge[tot]=z;//存放权值
    ne[tot]=head[x];//存放下一个点
    head[x]=tot;//存放起始点
}
queue<int> q;//定义队列
void spfa(int s)
{
    q.push(s);//将起点放入队列
    d[s]=0;//初始化起点的值
    v[s]=1;//标记起点
    while(q.size())//队列里面不为空，如果为空，则证明已经遍历整张图的所有边已经是最短的了
    {
        int x=q.front();//取出队列中的点  就是上一次更新的最小点
        q.pop();//释放刚刚取出的点
        v[x]=0;//取消不在队列的点
        for(int i=head[x];i;i=ne[i])//遍历整张图
        {
            int y=ver[i];//y为终点
            int w=edge[i];//w为权值
            if(d[y]>d[x]+w)//如果起点到y的距离大于起点到x的最短距离加上x到y的距离，则更新起点到y点的距离
            {
                d[y]=d[x]+w;//更新起点到y点的距离
                if(!v[y])//如果y点已经入队 则跳过
                {
                    q.push(y);//将y点入队
                    v[y]=1;
                }
            }
        }
    }
} 
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);//邻接表存图
    }
    for(int i=1;i<=n;i++)
    {
        d[i]=pow(2,31)-1;//初始化所有数组d
    }
    memset(v,0,sizeof(v));//初始化数组v
    d[s]=0;//起点到本身的距离为0
    spfa(s);//调用spfa
    for(int i=1;i<=n;i++)
    cout<<d[i]<<' ';//依次输出到各个点的最短路径
    return 0;
}