【专题】Johnson

发表于 分类于 ， 本文字数： 544 阅读时长 ≈ 1 分钟
图论专题，介绍Johnson算法

简介

Johnson算法是求解多源最短路的算法之一，核心操作是re-weight，适用于不包含负环（负权回路）的图。时间复杂度\(O(nm+nmlogm)\)。

Johnson算法

全源最短路常用方法是Floyd算法，时间复杂度\(O(n^{3})\)。当然我们也可以对每个顶点跑单源最短路。如果对每个顶点求一次Bellman-Ford算法，时间复杂度是\(O(n^{2}m)\)，似乎不如Floyd算法。如果是对每个顶点求一次Dijkstra算法，时间复杂度是\(O(nm+nmlogm)\)，看起来优于Floyd算法了。但是如何去除负边权的影响呢？

考虑一下直接把所有边权加个正数，但是显然不满足原图性质了：

直接加

这里提出一个re-weight操作，首先加上一个源点，并使其与所有顶点连通，新边权赋值为0，如下图：

加源

然后以新加顶点为源，跑Bellman-Ford算法，求出到其它顶点的最短路：

最短路

记录下最短路径长度h[] = {0, -3, 0, 0}，删除刚刚新增加的结点。然后对原图边权进行处理，使用以下方法更新边权：\(w'(u, v) = w(u, v) + (h[u] - h[v])\)。

处理

这时，负边权的影响就被消除了，可以愉快的使用Dijkstra算法了。（懒一下，正确性请自行证明）。

模板

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
const int inf = 0x3f3f3f3f;
const int mxn = 1e3 + 5;

struct E {
    int to, next, w;
} e[mxn];

int H[mxn], tot;

void add(int from, int to, int w) {
    e[tot] = {to, H[from], w};
    H[from] = tot++;
}

void graph_init(int n)
{
    for(int i=1; i<=n; i++)
        H[i] = -1;
    tot = 0;
}

int h[mxn], num[mxn];
bool vis[mxn];
queue<int> q;

void spfa_init(int n)
{
    for(int i=1; i<=n; i++){
        h[i] = inf;
        num[i] = 0;
    }
}

int spfa(int s, int n)
{
    h[s] = 0; q.push(s);
    num[s] = vis[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int i=H[u]; ~i; i=e[i].next){
            int v = e[i].to, w = e[i].w;
            if(h[u]+w < h[v]){
                h[v] = h[u]+w;
                if(!vis[v]){
                    q.push(v), vis[v] = 1;
                    if(++num[v] > n) return -1;
                }
            }
        }
    }
    return 0;
}

int dis[mxn];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

void dijkstra_init(int n)
{
    for(int i=1; i<=n; i++){
        vis[i] = 0;
        dis[i] = inf;
    }
}

void dijkstra(int s, int n)
{
    pq.push({dis[s]=0, s});
    while(!pq.empty()){
        int u = pq.top().second; pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i=H[u]; ~i; i=e[i].next){
            int v=e[i].to, w=e[i].w;
            if(!vis[v] && dis[u]+w < dis[v]){
                dis[v] = dis[u]+w;
                pq.push({dis[v], v});
            }
        }
    }
}

int DIS[mxn][mxn];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    graph_init(n);

    for(int i=1; i<=m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(u, v, w);
    }

    for(int i=1; i<=n; i++)
        add(0, i, 0);

    spfa_init(n);
    if(spfa(0, n) == -1)
    {
        printf("包含负权回路\n");
    }
    else
    {
        for(int u=1; u<=n; u++){
            for(int i=H[u]; ~i; i=e[i].next){
                e[i].w += h[u] - h[e[i].to];
            }
        }

        for(int i=1; i<=n; i++){
            dijkstra_init(n);
            dijkstra(i, n);
            for(int j=1; j<=n; j++){
                DIS[i][j] = dis[j] - h[i] + h[j];
                printf("%d ", DIS[i][j]);
            }
            printf("\n");
        }
    }

    return 0;
}


/*
Sample Input:

4 5
1 2 -3
2 3 2
1 4 3
2 3 4
3 4 1


Sample Output:

0 -3 -1 0
1061109570 0 2 3
1061109568 1061109565 0 1
1061109567 1061109564 1061109566 0

*/