Johnson全源最短路

发表于 | 分类于 ，

概述:

最为熟知的全源最短路算法肯定是floyd, 时间复杂度是$O(n^3)$.

但是当给出的图是稀疏图, 边权为非负值时, 可以直接跑n遍dijkstra, 时间复杂度是$O(nmlogn)$, 此时m(边数)与n(点数)同阶, 要比floyd更优.

但dijkstra不能正确求解带负权边的最短路, 对于带负权边的图我们需要经过预处理, 使得所有的边权非负. 这便是Johnson算法要做的.

实现:

Johnson算法引入了一个物理概念—势能. 将图G中点$i$的”势能”记为$h_i$.

G

为了求得$h_i$, 首先新建一个虚拟节点(设其编号为0).

G

接下来用Bellman-Ford(spfa)求出0号节点到各点的最短路, 即为$h_i$.

G

对于原图G中的某条边$\langle u,v \rangle$, 重新设置它的边权为$w \langle u,v \rangle -(h_v-h_u)$.

G'

接下来遍历起点, 跑n遍dijkstra即可.

时间复杂度为$O(nm+nmlogn)$

正确性证明:

需要证明的是两个命题, 即重构后的图上的最短路径和原图的最短路径一致, 以及重构后每条边的边权均为非负值.

证明1/2:

重构后的图中, 从$s$到$t$的一条路径$s \to p_1 \to p_2 \to \cdots \to p_k \to t$的长度为:

从这里可以看出”势能”这个名字的由来: 无论走哪条路径, 最后的$h_t-h_s$是不变的.

同时由于$h_t-h_s$是定值, 前面的部分为原图的路径长度, 因此重构后图上的每条路径都与原图相对应

证明2/2:

根据预处理(Bellman-Ford或spfa)以及三角形不等式, 对边$\langle u,v \rangle$, 有不等式$h_v \le h_u + w \langle u,v \rangle$.

移项即得$w’ \langle u,v \rangle = w \langle u,v \rangle -h_v+h_u \ge 0$, 即重构后的图边权均非负. 证毕.

代码:

(luogu5905)Johnson全源最短路模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int Mn(3050),Mm(10050);

//建图
int n,m;
struct edge
{
    int e,v,nt;
}ed[Mm];
int vs[Mn],ec(0);
void adde(int u,int v,int w)
{
    ed[++ec] = (edge){v,w,vs[u]};
    vs[u] = ec;
}

//求h
int h[Mn],inq[Mn];
bool isq[Mn];
bool spfa(int s)
{
    fill(h,h+Mn,static_cast<int>(1e9));
    queue<int> q;
    h[s] = 0; ++inq[s];
    q.push(s);
    while(!q.empty())
    {
        int xn(q.front()); q.pop();
        isq[xn] = false;
        if(inq[xn]>=n)  return false;
        for(int i(vs[xn]);i;i=ed[i].nt)
        {
            edge& e(ed[i]);
            if(h[e.e]>h[xn]+e.v)
            {
                h[e.e] = h[xn] + e.v;
                if(!isq[e.e])
                {
                    q.push(e.e);
                    isq[e.e] = true; ++inq[e.e];
                }
            }
        }
    }
    return true;
}

//堆优化dijkstra
struct qn
{
    int n,d;
    bool operator <(const qn& rhs) const	//小根堆
    { return d>rhs.d; }
};
int d[Mn];
bool isd[Mn];
void dij(int s)
{
    fill(d+1,d+n+2,static_cast<int>(1e9));
    memset(isd,0,sizeof isd);
    priority_queue<qn> pq;
    d[s] = 0;
    pq.push((qn){s,0});
    while(!pq.empty())
    {
        qn x(pq.top()); pq.pop();
        if(isd[x.n]) continue;
        isd[x.n] = true;
        for(int i(vs[x.n]);i;i=ed[i].nt)
        {
            edge& e(ed[i]);
            if(d[e.e]>d[x.n]+e.v-h[e.e]+h[x.n])
            {
                d[e.e] = d[x.n]+e.v-h[e.e]+h[x.n];
                pq.push((qn){e.e,d[e.e]});
            }
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i(1);i<=m;++i)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        adde(u,v,w);
    }
    for(int i(1);i<=n;++i)	//添加虚拟节点(这里编号是n+1)
        adde(n+1,i,0);
    if(!spfa(n+1))	//如果有负环
    {
        printf("-1");
        return 0;
    }
    for(int i(1);i<=n;++i)
    {
        long long ans(0);
        dij(i);
        for(int j(1);j<=n;++j)
        {
            if(d[j]!=1e9)   ans += 1ll*j*(d[j]+h[j]-h[i]);	//注意d[j]和原图最短路有区别
            else            ans += 1ll*j*d[j];
        }
        printf("%lld\n",ans);
    }
    return 0;
}