Johnson全源最短路

· · 个人记录

板子题：https://www.luogu.com.cn/problem/P5905

个人认为是最难的一个最短路算法了，因为实现中用到了很多其他的最短路

数据：

负权边：支持

判断负环：不支持

复杂度：NM\log M

(实际上是O(N·dijkstra)，这里采用堆优化dijkstra)

前置知识

没错要学这个最短路其他的都得会。 # 基本思路 通过复杂度可以看出，这个算法与 $n$ 遍 $dijkstra$ 一样快。 那为什么不用 $n$ 遍 $dijkstra$ 呢？有负权。 那怎么解决呢？重新标权值，且保证正确性。 加一个新点0，将0与每个点之间连一条长度为0的边。 然后求0到每个点的最短路，记0到 i 的最短路为$h_i$。 更新每个边$edge\_len(u,v)$的权值为$edge\_len(u,v)+h_u-h_v$。 三角形两边之和大于第三边，所以$edge\_len(u,v)+h_u≥h_v$。 ($\triangle SUV$有可能退化成线段$SV$，所以是$≥$) 所以这个图上每个边就都是非负的了，就可以跑 $n$ 边 $dijkstra$ 啦。 然后把每个源点的最短路$-h_u+h_v$还原回去，就是正确答案了。 # 正确性证明 设起始点为 $s$，终点为 $t

最短路：s\rightarrow p_0\rightarrow p_1\rightarrow p_2\rightarrow ...\rightarrow p_k\rightarrow t

原图中的最短路长度：w(s,p_0)+w(p_0,p_1)+w(p_1,p_2)+...+w(p_k,t)

新图中的最短路长度：w(s,p_0)+h_s-h_{p_0}+w(p_0,p_1)+h_{p_0}-h_{p_1}+w(p_1,p_2)+h_{p_1}-h_{p_2}+...+w(p_k,t)+h_{p_k}-h_t

你会发现，带 p 的项都消了!

则新图中最短路长度为：w(s,p_0)+w(p_0,p_1)+w(p_1,p_2)+...+w(p_k,t)+h_s-h_t

又因为两点间势能的差为定值，即h_s-h_t为定值，

所以新图中的最短路与原图中的最短路对应。

实现思路

求0到每个点的最短路，因为图中有负权，可以用bellman-ford或spfa

但这样连出来的图一定是个菊花图，选择这两种的效率没什么区别。

而且这不影响最后的时间复杂度，时间复杂度由n次dijkstra决定。

然后枚举点u，再枚举所有能到达的点v，更新u到v的权值w。

最后跑n遍dijkstra即可。

另外，对于这道题，要判断负环。

可以在求0到每个点的最短路时顺便用bellman-ford或者spfa判断负环

代码

#include <iostream>
#include <queue>
#include <utility>
#include <functional>
#include <cstring>
using namespace std;
struct Edge
{
    int v, w, nxt;
}edge[9001];
int n, m, u, v, w, head[3001], cnt;long long dis[3001], h[3001], ans;
void add(int u, int v, int w) //加边
{
    ++cnt;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
void dijkstra(int s) //正常的dijkstra
{
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;bool vis[3001];memset(vis, 0, sizeof vis);
    for(int i = 1;i <= n;++i) dis[i] = 1e9;
    dis[s] = 0;q.push(make_pair(0, s));
    while(!q.empty())
    {
        int u = q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u];i;i = edge[i].nxt)
            if(dis[edge[i].v] > dis[u] + edge[i].w)
            {
                dis[edge[i].v] = dis[u] + edge[i].w;
                q.push(make_pair(dis[edge[i].v], edge[i].v));
            }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0;i < m;++i)
        cin >> u >> v >> w, add(u, v, w);
    for(int i = 1;i <= n;++i)
        add(0, i, 0), h[i] = 1e9; //加从0到每个点的边，权值为0
    h[0] = 0;
    for(int i = 1;i < n;++i) //开始bellman-ford
        for(int u = 0;u <= n;++u)
            for(int j = head[u];j;j = edge[j].nxt)
                h[edge[j].v] = min(h[edge[j].v], h[u] + edge[j].w);
    for(int u = 1;u <= n;++u) //判负环
        for(int i = head[u];i;i = edge[i].nxt)
            if(h[edge[i].v] > h[u] + edge[i].w)
            {
                cout << -1;
                return 0;
            }
    for(int u = 1;u <= n;++u)
        for(int i = head[u];i;i = edge[i].nxt)
            edge[i].w = edge[i].w + h[u] - h[edge[i].v]; //更新权值
    for(int u = 1;u <= n;++u)
    {
        dijkstra(u);ans = 0;
        for(int v = 1;v <= n;++v)
            if(dis[v] == 1e9) ans += v * 1e9;
            else ans += v * (dis[v] - h[u] + h[v]); //还原权值
        cout << ans << endl;
    }
    return 0;
}