【图论】Johnson全源最短路笔记

C_liar · 2022-08-03 20:45:46 · 算法·理论

简介

用于稀疏图求解全源最短路。
时间复杂度(优先队列) O(VE\log E)，使用斐波那契堆可优化至 O(VE+V^2\log V)，稀疏图上渐进复杂度优于 \text{Floyd-Warshall} 算法。
返回一个包含所有结点对的最短路径权重的矩阵或报告存在负环。

原理

重新赋予权重 \text{reweight}

若图 G=(V,E) 不存在负边权，则对每个结点运行 \text{Dijkstra} 算法求解。若图 G 包含权重为负值的边，但无负环，那么只要计算出一组新的非负权重值，对每个结点使用同样的方法即可。

新赋予的权重 w' 必须满足以下两个性质:

对于所有结点对 u,\space v\in V ，一条路径 p 是在使用权重函数 w 时从结点 u 到结点 v 的一条最短路径，当且仅当 p 是在使用权重函数 w' 时从 u 到 v 的最短路径。
对于所有的边 (u,\space v) ，新权重 w'(u,\space v) 非负。

具体实现

新建一个虚拟结点 s ，从 s 出发，向 \forall i \in V 建立边权为零的有向边 (s,\space i) ,设从 s 到 i 的最短路径长度为 h(i) ,则对于每条边 (u,\space v)\in E，定义

w'(u,v)=w(u,v)+h(u)-h(v)

设 p=\langle v_1,v_2,\dots,v_k \rangle 为 v_1 到 v_k 的一条路径，则有一条引理：当 p 是使用权重函数 w 时从 v_1 到 v_k 的最短路径，当且仅当 p 是使用权重函数 w' 时从 v_1 到 v_k 的最短路径。

由裂项相消和可得，w'(p)=w(p)+h(v_1)-h(v_k)。

由于 h(v_1) 和 h(v_k) 取值不与具体路径有关，故引理得证。

对于环路 c=\langle v_1,v_2,\dots,v_k,v_1 \rangle ，w'(c)=w(c) ，故当 w(c)\lt 0 时， w'(c)\lt 0。

故满足性质 1。

而根据三角形不等式，定义 E'=E\bigcup \{(s,\space v):v\in V\} 为新图的边集，对于所有的边 (u,\space v)\in E' 有 h(v)\le h(u)+w(u,v) ，因此，有 w'(u,\space v)=w(u,\space v)+h(u)-h(v)\ge 0 。

故满足性质 2。

代码实现

题目来源：【模板】Johnson 全源最短路

伪代码：略。

C++：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
const int __=6e3+10;
const int _=3e3+10;
const int inf=2147483647;
using namespace std;

int n,m;

struct Edge{
    int to[__<<1],dis[__<<1],next[__<<1],head[_],tot;
    void add(int u,int v,int w){
        to[++tot]=v,dis[tot]=w,next[tot]=head[u],head[u]=tot;
    }
}e;

struct node{
    int u,dis;
    node(){}
    node(int x,int w){u=x,dis=w;}
    bool operator <(const node &a)const{
        return dis>a.dis;
    }
};

int h[_];bool vis[_];
int ct[_];
queue<int> q1;
priority_queue<node> q;

bool spfa(){
    for(int i=1;i<=n;i++) h[i]=inf;
    q1.push(0);vis[0]=1;
    while(q1.size()){
        int u=q1.front();q1.pop();
        vis[u]=0;
        for(int i=e.head[u],y;i;i=e.next[i]){
            if((long long)h[y=e.to[i]]>(long long)h[u]+e.dis[i]){
                h[y]=h[u]+e.dis[i];
                ct[y]=ct[u]+1;
                if(ct[y]>n) return 1;
                if(!vis[y]){
                    vis[y]=1;
                    q1.push(y);
                }
            }
        }
    }
    return 0;
}

int dis[_];
void Dijkstra(int s){
    for(int i=1;i<=n;i++) dis[i]=inf;
    memset(vis,0,sizeof vis);
    dis[s]=0;
    q.push(node(s,0));
    while(q.size()){
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=e.head[u],v;i;i=e.next[i]){
            if(dis[v=e.to[i]]>dis[u]+e.dis[i]){
                dis[v]=dis[u]+e.dis[i];
                if(!vis[v]) q.push(node(v,dis[v])); 
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        e.add(u,v,w);
    }
    for(int i=1;i<=n;i++) e.add(0,i,0);
    if(spfa()){
        puts("-1");return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=e.head[i];j;j=e.next[j]){
            e.dis[j]+=h[i]-h[e.to[j]];
        }
    }
    for(int i=1;i<=n;i++){
        Dijkstra(i);
        long long ans=0;
        for(int j=1;j<=n;j++){
            if(dis[j]==inf) ans+=(long long)j*(int)1e9;
            else ans+=(long long)j*(dis[j]+h[j]-h[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

参考资料

《算法导论》
[洛谷日报#242]Johnson 全源最短路径算法学习笔记 -StudyingFather的博客

【图论】Johnson全源最短路 笔记

简介

原理

代码实现

参考资料

【图论】Johnson全源最短路笔记