最短路与最小生成树算法

• 性质1：边权为正的图，最短路不会经过重复的点和重复的边
• 性质2：边权为正的图，任意最短路 经过的点不会超过n，经过的边不会超过n-1
• 注意：存在负环的图没有最短路

一：Floyd算法（多源最短路）

1.时间复杂度：O(n^3)
2.边权可正可负
3.邻接矩阵存图
4.实现如下：

1.初始化邻接矩阵

    memset(dis,0x3f,sizeof dis);//不连通的点为无穷大
    for(int i=1;i<=n;i++)dis[i][i]=0;//到自己的距离

2.读入每条边

    dis[u][v]=min(dis[u][v],w);

3.动态规划递推

    for(int k=1;k<=n;k++)//动态规划：考虑仅经过前k个点的最短路
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//考虑新加入的k点能否更新最短路

5.Floyd算法的应用

1.求任意两点距离或任意两点是否连通
2.在正权无向图，求一个最小权值和的环（环中点大于3个）

    int ans=inf;
    for(int k=1;k<=n;k++)//动态规划：考虑仅经过前k个点的最短路
    {
        //考虑环上编号最大的结点k，i,j两两配对：dis[i][j]+g[i][k]+g[k][j]为一个环的边权和
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
                ans=min(ans,dis[i][j]+g[i][k]+g[k][j]);

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//考虑新加入的k点能否更新最短路
    }

二：Bellman_ford算法（单源最短路）

1.时间复杂度：O(n*m)
2.边权可正可负
3.edge[N]数组存边(u,v,w)
4.必须使用backup数组备份单源最短路dis数组
5.实现如下：

1.初始化
memset(dis,0x3f,sizeof dis);//初始化单源最短路dis数组
dis[s]=0;//源点

2.Bellman_ford：(n-1)轮，每一轮遍历所有边进行松弛操作（因为任意最短路不会超过n-1条边）
for(int i=1;i<=n-1;i++)
{
    memcpy(pre_dis,dis,sizeof dis);//备份dis数组用于更新

    bool flag=false;
    for(int j=1;j<=m;j++)//遍历每一条边进行松弛
    {
        if(dis[e[j].v]>pre_dis[e[j].u]+e[j].w)
        {
            dis[e[j].v]=pre_dis[e[j].u]+e[j].w;
            flag=true;
        }
    }
    if(!flag)break;//此轮没有边可以再松弛就直接退出
}

6.Bellman_ford算法的应用

1.求单源最短路或有边数限制的单源最短路
2.判断是否存在负环：第n轮还能更新dis数组说明存在负环（起点必须是超级源点）
（为保证能从起点能达到负环，应该从超级源点（到其他所有点都是0距离）开始）

    bool bellmon_ford()
    {
        //超级源点作为起点判负环：单源最短路dis全默认为0即可
        for(int i=1;i<=n-1;i++)//最多经过k条边
        {
            memcpy(pre_dis,dis,sizeof dis);//备份dis数组用于更新

            bool flag=false;
            for(int j=1;j<=m;j++)//遍历每一条边进行松弛
            {
                if(dis[e[j].v]>pre_dis[e[j].u]+e[j].w)
                {
                    dis[e[j].v]=pre_dis[e[j].u]+e[j].w;
                    flag=true;
                }
            }
            if(!flag)return false;//此轮没有边可以再松弛直接不存在负权环
        }

        //第n轮，如果还能更新则存在负环
        for(int j=1;j<=m;j++)//遍历每一条边进行松弛
            if(dis[e[j].v]>dis[e[j].u]+e[j].w)return true;

        return false;
    }

三：Spfa算法（单源最短路）（队列优化版bellman_ford）

1.时间复杂度：最坏情况O(n*m)，最好情况O(m)
2.边权可正可负
3.邻接表/邻接矩阵存图
4.使用queue（与bfs类似）
5.实现如下：

void spfa(int s) 
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;

    queue<int>q;
    q.push(s);
    st[s]=true;

    while(!q.empty())
    {
        int t=q.front();
        q.pop();

        st[t]=false;//取消标记，后续t点还能被标记入队更新其它点

        for(int i=h[t];i!=-1;i=ne[i])//用t来更新其他点 
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];//更新j点的最短距离
                if(!st[j])//如果j点不在队列中，则j入队用来后续更新其他点 
                {
                    q.push(j); 
                    st[j]=true;//防止重复加入 
                }
            }
        }
    }
}

6.Spfa算法的应用

1.求单源最短路
2.判断是否存在负环：某个点被加入大于n次就说明存在负环（起点必须是超级源点）

bool spfa(int s) 
{
    memset(dis,0x3f,sizeof dis);

    queue<int>q;
    for(int i=1;i<=n;i++)//将每个点加入（避免连通分量大于1不能遍历到整个图）
    {
        st[i]=true;
        q.push(i);
        dis[i]=0;
    }

    while(!q.empty())
    {
        int t=q.front();
        q.pop();

        st[t]=false;//取消标记，后续t点还能被标记入队更新其它点

        for(int i=h[t];i!=-1;i=ne[i])//用t来更新其他点 
        {
            int j=e[i];
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i];//更新j点的最短距离
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n)return true;//大于等于n+1次则一定存在负环
                if(!st[j])//如果j点不在队列中，则j入队用来后续更新其他点 
                {
                    q.push(j); 
                    st[j]=true;//防止重复加入 
                }
            }
        }
    }

    return false;//不存在负环
}

四：Dijkstra算法（单源最短路）

1.时间复杂度：朴素版O(n^2)，堆优化版O(mlogm)
2.边权只能为正
3.邻接表/邻接矩阵存图
4.每次找未标记且距源点最近的点标记
5.使用优先队列priority_queue（堆优化）
6.实现如下：

//朴素版
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;

    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)//取距离源点最近且未标记的点t
            if(!st[j] && (t==-1 || dis[j]<dis[t]))t=j;

        st[t]=true;//标记，t点最短路已确定

        for(int j=h[t];j!=-1;j=ne[j])//以t.y点向外更新其他点到源点的距离
        {
            int k=e[j];
            if(dis[k]>dis[t]+w[j])dis[k]=dis[t]+w[j];
        }
    }

}

//小根堆优化版
void dijkstra(int s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;

    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({dis[s],s});

    while(!q.empty())
    {
        auto t=q.top();//取距离源点最近且未标记的点t.y
        q.pop();

        if(st[t.y])continue;//防止重边和自环
        st[t.y]=true;//标记，t.y点最短路已确定

        for(int i=h[t.y];i!=-1;i=ne[i])//以t.y点向外更新其他点到源点的距离
        {
            int j=e[i];
            if(dis[j]>dis[t.y]+w[i])
            {
                dis[j]=dis[t.y]+w[i];
                q.push({dis[j],j});//入队，用于后续更新最短路
            }
        }
    }
}

五：Kruskal算法（最小生成树）

1.时间复杂度：O(m*logn)
2.贪心：对边从小到大排序
3.并查集：判断是否在一个连通块中
4.edge[N]数组存边
5.实现如下：

    int res=0,cnt=0;
    for(int i=1;i<=m;i++)//从小到大遍历每一条边
    {
        int a=e[i].u,b=e[i].v,c=e[i].w;
        if(find(a)!=find(b))//不在一个连通块中 
        {
            p[find(a)]=find(b);
            res+=c;
            cnt++;//边数+1 
        }
    }

    if(cnt<n-1)cout<<"impossible";//边数不足n-1则不存在最小生成树
    else cout<<res;

六：Prim算法（最小生成树）

1.时间复杂度：O(n^2)
2.贪心：每次找未标记且距源点最近的点标记
3.邻接矩阵/邻接表存图
4.实现如下：

    int prim(int s)
    {
        memset(dis,0x3f,sizeof dis);//dis：距离已标集合最短距离
        dis[s]=0;

        int res=0;
        for(int i=1;i<=n;i++)//n轮标记n个点
        {
            int t=-1;
            for(int j=1;j<=n;j++)
                if(!st[j] && (t==-1 || dis[j]<dis[t]))t=j;//t:未标记且距已标记集合最近的点

            if(dis[t]==inf)return inf;//不能标全n个点，无最小生成树
            res+=dis[t];
            st[t]=true;

            for(int j=1;j<=n;j++)//t点向外更新其他点
                if(dis[j]>e[t][j])dis[j]=e[t][j];
        }

        return res;
    }