寒假集训Day 2

In the past two days, we have learned four shortest path algorithms: Dijkstra, Floyd, Bellman Ford, and SPFA. The detailed content is as follows
这两天我们学了Dijkstra，Floyd，Bellman-Ford，SPFA四个最短路径算法，详细内容如下。

Dijkstra算法

此算法无法处理负权边！！！
单源最短路径
代码如下（链式前向星+堆优化）

int head[110000],cnt,dis[110000],vis[110000],ans;
struct Edge{
    int next,to,w;
}a[10000000];
void add(int x,int y,int z)
{
    a[++cnt].next=head[x];
    head[x]=cnt;
    a[cnt].to=y;
    a[cnt].w=z;
}
void dijkstra(int h)
{
    typedef pair<int,int> pr;
    priority_queue<pr,vector<pr>,greater<pr> > q;
    q.push({0,h});
    memset(dis,0x3f3f3f,sizeof dis);
    dis[h]=0;
    while(q.size())
    {
        pr t=q.top();
        q.pop();
        int x=t.second;
        int u=t.first;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=a[i].next)
        {
            int y=a[i].to;
            if(!vis[y] && dis[y]>dis[x]+a[i].w)
            {
                dis[y]=dis[x]+a[i].w;
                q.push({dis[y],y});
            }
        }
    }
}

Floyd算法

可处理多源最短路径

for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
            }
        }
    }

Bellman-Ford算法

单源最短路径，但时间复杂度高。

SPFA算法

Bellman-Ford算法的升级版
单源最短路径，可处理负权边

int head[500000],cnt;
struct Edge{
    int next,to,w;
}a[10000000];
void add(int x,int y,int z)
{
    a[++cnt].next=head[x];
    head[x]=cnt;
    a[cnt].to=y;
    a[cnt].w=z;
}
void SPFA(int h)
{
    memset(dis,0x3f3f3f,sizeof dis);
    queue<int>q;
    dis[h]=0;
    vis[h]=1;
    q.push(h);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=a[i].next)
        {
            int y=a[i].to;
            if(dis[x]+a[i].w<dis[y])
            {
                dis[y]=dis[x]+a[i].w;
                if(!vis[y])
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}