全源最短路 Johnson算法

本文写于较早时期，之前对Dijkstra的理解不是很透彻

已经修改了部分显然错误的内容，有空会再仔细检查的

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

题意简述：给定一个包含 \(n\) 个结点和 \(m\) 条带权边的有向图，求全源最短路，可能有负权重的边、重边、自环，部分数据卡 SPFA 算法（还特地针对了SLF优化）

题意很明确，就是卡SPFA、Dijkstra、Floyd的

这题用SPFA可以被卡成\(O(n^2m)\)，Dijkstra不能处理负权重的边，Floyd\(O(n^3)\)肯定超时

说了这么多，就是为了引出我们要讲的 Johnson 算法

Johnson算法可以判断给定的图中有无负环，在无负环时能给出全源最短路时间复杂度 \(O(n^2\log m)\) （Dijkstra采用优先队列优化，详细的分析可以看这边link）

Johnson算法的核心为重新赋予权值，使得边权变成非负的新边权，而在运行过程中以Bellman-Ford和Dijkstra（以下提到的Dijkstra都用优先队列优化）作为自己的子程序

一、算法原理

以下推导过程部分参照《算法导论》

对于给定有向图 \(G=(V,E)\) ，权重函数为 \(w:E \rightarrow R\) ，如果所有的边权重都为非负值，则只需在每一个结点上跑Dijkstra即可，时间复杂度\(O(V^2\log E)\)；如果存在边权重为负值的边，但没有负环，则我们只需要预处理出一种新的权重函数 \(w^{\prime}:E \rightarrow R\) 使得所有的边权重为非负值再跑Dijkstra即可

则新的权重函数 \(w^{\prime}\) 一定满足以下两个条件：

1. 对于结点 \(u,v \in V\) ，路径 \(p\) 为使用权重函数 \(w^{\prime}\) 时 \(u\) 到 \(v\) 的一条最短路径，当且仅当 \(p\) 为使用权重函数 \(w\) 时 \(u\) 到 \(v\) 的一条最短路径
2. 对于任何边 \((u,v) \in E\) ，\(w^{\prime}(u,v)\) 为非负值 （Dijkstra不可以处理负权重的边）

设函数 \(h:V\rightarrow \mathbb{R}\) 将结点映射到实数上

对于任何边\((u,v) \in E\)，定义 \(w^{\prime}(u,v) = w(u,v) + h(u) - h(v)\)

我们先假设图 \(G\) 没有负环，设路径 \(p\) 为使用权重函数 \(w^{\prime}\) 时 \(v_0\) 到 \(v_k\)的一条最短路径\((v_0,v_k \in V)\) ，当且仅当 \(p\) 为使用权重函数 \(w\) 时 \(v_0\) 到 \(v_k\) 的一条最短路径

则可以证明 \(w^{\prime}(p) = w(p) + h(v_0)-h(v_k)\) \[ \begin{aligned} w^{\prime}(p)&=\sum\limits_{i=1}^{k}{w^{\prime}(v_{i-1},v_i)} \\\\&= \sum\limits_{i=1}^{k}{(w(v_{i-1},v_i)+h(v_{i-1})-h(v_i))} \\\\&=\sum\limits_{i=1}^{k}{w(v_{i-1},v_i)}+h(v_0)-h(v_k) \\\\&= w(p)+h(v_0)-h(v_k) \end{aligned} \] 因为 \(h\) 为将结点映射到实数上的函数，函数的值不受边权重的影响，所以对于一条为使用权重函数 \(w\) 时 \(v_0\) 到 \(v_k\) 比 \(p\) 要长的路径 \(q\) ，在使用权重函数 \(w^{\prime}\) 时 \(q\) 一定比 \(p\) 长

我们再来看看负环的问题，对于环\(c = \langle v_0, v_1, ... v_k\rangle\) ，其中 \(v_0 = v_k\) ，则有 \(w^{\prime}(c) = w(c) + h(v_0) -h(v_k) = w(c)\)

则对于 \(c\) 使用权重函数 \(w\) 时为负环，当且仅当使用权重函数 \(w\) 时为负环

那么 \(h\) 函数该如何处理呢？

我们可以新建一个虚拟结点 \(s\) ，并将 \(s\) 和其他所有结点建边权重为 \(0\) 的边，在 \(s\) 结点跑一次Bellman-Ford（SPFA当然可以），求出 \(s\) 到其他结点的最短路，则对于任何 \(v \in V\) ， \(h(v)\) 的值即为 \(s\) 到 \(v\) 的最短路径长，在跑的过程中如果一条路径中某个结点被松弛超过 \(n\) 次，则一定存在负环，并返回存在负环的信息（SPFA判负环的方法就不延伸了）

因为 \(s\) 结点入度为 \(0\) ，所以其他的路径中不会包含 \(s\) 结点

那么为什么无负环时使用权重函数 \(w^{\prime}\) ，边权重一定为非负呢？

设现在的图为 \(G^{\prime} = (V^{\prime},E^{\prime})\) ，\(V^{\prime} = V \cup \{s\}\) ，\(E^{\prime} = E \cup \{(s,v),v\in E\}\)

根据三角形不等式，可知对于任意结点 \(u,v \in V^{\prime}\) ，若 \(\exists (u,v) \in E^{\prime}\)，则有 \[ \begin{aligned} h(u) + w(u,v) \ge h(v)&\Rightarrow w(u,v) + h(u) - h(v) \ge 0 \\\\&\Rightarrow w^{\prime}(u,v) \ge 0 \end{aligned} \] 现在我们只需要在每个结点上跑一次Dijkstra即可

时间复杂度 \(O(V^2 \log E)\) （SPFA时间复杂度最坏 \(O(VE)\) ，预处理时间复杂度 \(O(VE)\) ）

二、参考代码

模板题代码如下 （注：输出按该题要求写的）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 1000000000
#define MAXN (int)(3e3+15)
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch==^{\prime}-^{\prime})f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){pc(^{\prime}-^{\prime});k=-k;}
    if(k>9)write(k/10);
    pc(k%10+^{\prime}0^{\prime});
}
struct Edge
{
    int u,v,w,next;
}e[MAXN<<2];
struct node
{
    int u,dis;
    bool operator<(const node &o)const
        {return dis>o.dis;}
};
int n,m,pos=1,head[MAXN];
int h[MAXN],d[MAXN],vis[MAXN],cnt[MAXN],ans;
void addEdge(int u,int v,int w)
{
    e[pos]={u,v,w,head[u]};
    head[u]=pos++;
}
bool spfa()
{
    queue<int> q;
    fill(h+1,h+1+n,INF);
    q.push(0);
    vis[0]=1;h[0]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(h[v]>h[u]+e[i].w)
            {
                h[v]=h[u]+e[i].w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                    if(++cnt[v]>n) // n+1结点
                        return 0;
                }
            }
        }
    }
    return 1;
}
void dijkstra(int st)
{
    priority_queue<node> q;
    fill(d+1,d+1+n,INF);
    memset(vis,0,sizeof(vis));
    q.push({st,0});
    d[st]=0;
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(d[v]>d[u]+e[i].w)
            {
                d[v]=d[u]+e[i].w;
                q.push({v,d[v]});
            }
        }
    }
}
signed main()
{
    read(n);read(m);
    for(int i=1,u,v,w; i<=m; i++)
    {
        read(u);read(v);read(w);
        addEdge(u,v,w);
    }
    for(int i=1; i<=n; i++)
        addEdge(0,i,0);
    if(!spfa())return puts("-1"),0;
    for(int i=1; i<pos; i++)
        e[i].w+=h[e[i].u]-h[e[i].v];
    for(int i=1; i<=n; i++)
    {
        dijkstra(i);
        int ans=0;
        for(int j=1; j<=n; j++)
        {
            if(d[j]==INF)
                ans+=j*INF;
            else
                ans+=j*(d[j]-(h[i]-h[j]));
        }
        write(ans);pc(^{\prime}\n^{\prime});
    }
    return 0;
}