路径问题

亿方通行 · 2021-04-10 15:52:14 · 个人记录

全源最短路

Floyd

void floyd(){
    for(int i=0;i<maxn;Dis[i][i]=0,i++) for(int j=0;j<maxn;j++) Dis[i][j]=inf;
    for(int k=1;k<=n;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]);
}

模板题

Johnson

重载运算符

bool operator < (Node const x ,Node const y){
    return x.dis>y.dis;
}

核心代码

bool spfa(int s){
    for(int i=0;i<=n;i++) H[i]=inf,Cnt[i]=Vis[i]=0;
    Q.push(s); Vis[s]=1; H[s]=0;
    while(!Q.empty()){
        int u=Q.front(); Q.pop(); Vis[u]=0;
        for(int i=Pre[u];i;i=E[i].next){
            int v=E[i].to,w=E[i].w;
            if(H[v]>H[u]+w){
                H[v]=H[u]+w;
                Cnt[v]=Cnt[u]+1;
                if(Cnt[v]>n) return 1;
                if(!Vis[v]) Vis[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}

void dijkstra(int s){
    for(int i=1;i<=n;i++) Dis[i]=inf,Vis[i]=0;
    Pq.push((Node){s,0}); Dis[s]=0; 
    while(!Pq.empty()){
        int u=Pq.top().id; Pq.pop();
        if(Vis[u]) continue;
        Vis[u]=1;
        for(int i=Pre[u];i;i=E[i].next){
            int v=E[i].to,w=E[i].w;
            if(Dis[v]>Dis[u]+w){
                Dis[v]=Dis[u]+w;
                Pq.push((Node){v,Dis[v]});
            }
        }
    }
}

void johnson(){
    spfa(0);
    for(int i=1;i<=n;i++) dijkstra(i);
}

模板题

单源最短路

Dijkstra

重载运算符

bool operator < (Node const x ,Node const y){
    return x.dis>y.dis;
}

堆优化 + vector + 最短路计数

void dijkstra(){
    int curr;
    Dis[1]=0;
    Cnt[1]=1;
    Pq.push((Edge){1,0
    });
    while(!Pq.empty()){
        curr=Pq.top().id;
        Pq.pop();
        if(Vis[curr]) continue;
        Vis[curr]=1;
        for(int i=0;i<V[curr].size();i++){
            if(Dis[curr]+V[curr][i].w<Dis[V[curr][i].id]){
                Dis[V[curr][i].id]=Dis[curr]+V[curr][i].w;
                Cnt[V[curr][i].id]=Cnt[curr];
                Pq.push((Edge){V[curr][i].id,Dis[V[curr][i].id]
                });
            }
            else if(Dis[curr]+V[curr][i].w==Dis[V[curr][i].id]){
                Cnt[V[curr][i].id]+=Cnt[curr];
            }
        }
    }
}

模板题

堆优化 + 链式前向星

void dijkstra(int s){
    for(int i=1;i<=n;i++) Dis[i]=inf,Vis[i]=0;
    Pq.push((Node){s,0}); Dis[s]=0;
    while(Pq.size()){
        int u=Pq.top().id; Pq.pop();
        if(Vis[u]) continue;
        Vis[u]=1;
        for(int i=Pre[u];i;i=E[i].next){
            int v=E[i].to,w=E[i].w;
            if(Dis[v]>Dis[u]+w){
                Dis[v]=Dis[u]+w;
                Pq.push((Node){v,Dis[v]});
            }
        }
    }
}

模板题

SPFA

链式前向星 + 判负环

PS： 若求最长路，则为判正环

bool spfa(int s){
    for(int i=0;i<maxn;i++) Dis[i]=inf,Vis[i]=Cnt[i]=0;
    Q.push(s); Vis[s]=1; Dis[s]=0; 
    while(!Q.empty()){
        int u=Q.front(); Q.pop(); Vis[u]=0; 
        for(int i=Pre[u];i;i=E[i].next){
            int v=E[i].to,w=E[i].w;
            if(Dis[v]>Dis[u]+w){
                Dis[v]=Dis[u]+w;
                Cnt[v]=Cnt[u]+1;
                if(Cnt[u]>=n) return 0;
                if(!Vis[v]) Q.push(v),Vis[v]=1;
            }
        }
    }
    return 1;
}

模板题

单源次短路（严格）

Dijkstra

void dijkstra(){
    for(int i=1;i<=n;i++) Dis[i]=Dis2[i]=inf;
    Pq.push((Node){1,0}); Dis[1]=0;
    while(Pq.size()){
        int u=Pq.top().id; Pq.pop();
        for(int i=Pre[u];i;i=E[i].next){
            int v=E[i].to,w=E[i].w;
            if(Dis[v]>Dis[u]+w){
                Dis2[v]=Dis[v];
                Dis[v]=Dis[u]+w;
                Pq.push((Node){v,Dis[v]});
            }
            else if(Dis2[v]>Dis[u]+w&&Dis[v]!=Dis[u]+w){
                Dis2[v]=Dis[u]+w;
                Pq.push((Node){v,Dis[v]});
            }
            if(Dis2[v]>Dis2[u]+w) Dis2[v]=Dis2[u]+w;
        }
    }
}