数据结构第8讲最小生成树、最短路、关键路径

第8讲最小生成树、最短路、关键路径

1.最小生成树 MST

无向图

不一定唯一

唯一条件：任意环中边权都不同

(1) Prim

朴素： $O(n^2)$ 稠密图

堆优化： $O(mlogn)$ 稀疏图少用

AcWing 858. Prim算法求最小生成树

S:当前已经在联通块中的所有点的集合

dist[i] = inf

for n 次
找到不在s集合中，距离s集合最近的点t
将这个点t放入集合中
利用这个点t，更新不在集合中的点

联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离

Prim算法与Dijkstra算法的区别
Dijkstra算法是更新不在集合中的点离起点的距离

dist[j]=min(dist[j], dist[t]+g[t][j])

Prim是更新不在集合中的点离集合S的距离

dist[j] = min(dist[j], g[t][j])

c++:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 505, INF = 0x3f3f3f3f;
int n,m;
int g[N][N], dist[N]; //dist存储其他点到S的距离
bool st[N];


int prim(){

    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    int res = 0;
    for(int i=0;i<n;i++) // n个点
    {
        // 寻找离集合S最近的点  
        int t  = -1 ;
        for(int j = 1; j <=n ;j++)
            if(!st[j] && ( t==-1 || dist[t]>dist[j] ) )
                t = j ; // 更新t 

        // 当前可选的最短路径的点距离都是INF 说明不联通，return
        if(dist[t] == INF ) return INF;

        st[t]= true;

        res += dist[t];
        //利用这个点t， 更新不在集合中的点
        for(int j = 1;j<=n;j++)
            dist[j] = min(dist[j],g[t][j]);


    }

    return res;
}

int main()
{
    cin>>n>>m;
    memset(g,0x3f, sizeof g);
    while (m -- ){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int res = prim();
    if(res == INF) puts("impossible");
    else cout<<res<<endl;

    return 0;

}

(2) Kruskal

并查集笔试不考

$O(mlogn)$

看边权，每次看最小边权的边，加后是否形成环，不形成环可加

2.最短路

(1) 单源最短路 Dijkstra

AcWing 849. Dijkstra求最短路 I

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 505,INF = 0x3f3f3f3f;
int n,m;
int g[N][N],dist[N];
bool st[N];

int dij(){

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i ++ ){
        // n个点
        int t  =-1 ;
        for(int j = 1;j<=n;j++){
            if( !st[j]&& (t==-1|| dist[t]>dist[j] ) )
            t = j;
        }

        st[t] = true;

        // 更新
        for (int j = 1; j <= n; j ++ ){

            dist[j] = min(dist[j],dist[t]+ g[t][j]);

        }



    }

    return dist[n];
}

int main()
{
    cin>>n>>m;
    memset(g, INF, sizeof g);
    while (m -- ){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);

    }

    int res = dij();
    if(res == INF) puts("-1");
    else cout<<res<<endl;


    return 0;
}

(2) 多源汇最短路 Floyd

AcWing 854. Floyd求最短路

$O(n^3)$

实际上是dp的思想，笔试不考dp，了解算法即可

$d[i][j] = min(d[i][j], d[i][k] + d[k][j])$

1->2-> 3 与 1->3 比较，更新

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 205,INF = 0x3f3f3f3f;
int n,m,Q;
int d[N][N];
int main()
{
    
    
    cin>>n>>m>>Q;
    
    memset(d, 0x3f, sizeof d);
    for(int i = 1;i<=n; i++ ) d[i][i] = 0;
    
    while (m -- ){
        
        
        int a,b,c;
        
        cin>>a>>b>>c;
        
        d[a][b] = min(d[a][b],c);
        
        
    }
    
    for(int k= 1;k<=n;k++)
        for(int i = 1;i<=n;i++)
            for(int j = 1;j<=n;j++)
                d[i][j] = min( d[i][j], d[i][k] + d[k][j] );
    
    
    
    while(Q--){
        int x,y;
        cin>>x>>y;
        if(d[x][y]>INF/2) puts("impossible");
        else cout<<d[x][y]<<endl;
    }
    
    
    
    return 0;
}