Johnson 全源最短路径算法

简单来说就是 [[图论/spfa]] 与 [[图论/dijkstra]] 连用

\(Johnson\) 算法则通过另外一种方法来给每条边重新标注边权。

我们新建一个虚拟节点（在这里我们就设它的编号为 \(0\)）。从这个点向其他所有点连一条边权为 \(0\) 的边。

接下来用 \(Bellman-Ford\) 算法求出从 \(0\) 号点到其他所有点的最短路，记为 \(h_i\)。

假如存在一条从 \(u\) 点到 \(v\) 点，边权为 \(w\) 的边，则我们将该边的边权重新设置为 \(w+h_u-h_v\)。

接下来以每个点为起点，跑 \(n\) 轮 \(Dijkstra\) 算法即可求出任意两点间的最短路了。

一开始的 \(Bellman-Ford\) 算法并不是时间上的瓶颈，若使用 \(priority_queue\) 实现 \(Dijkstra\) 算法，该算法的时间复杂度是 \(O(nm\log m)\)。

负环判断中存在的常见误区 需要注意的是，以 \(S\) 点为源点跑 \(Bellman-Ford\) 算法时，如果没有给出存在负环的结果，只能说明从 \(S\) 点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 \(0\) 的边，然后以超级源点为起点执行 \(Bellman-Ford\) 算法。

1 【模板】全源最短路（Johnson）

#include<bits/stdc++.h>
using namespace std;
#define pll pair<int,int>
#define int long long
const int inf = 1e9;
int n,m;
struct{
    int v, w, next;
} a[10010];
int head[5010],dis[5010],h[5010],cnt[5010];
bool vis[5010];
int edge;
void add(int u,int v,int w)
{
    a[++edge].v = v;
    a[edge].w = w;
    a[edge].next = head[u];
    head[u] = edge;
}
bool spfa()
{
    memset(h, 0x3f, sizeof h);
    queue<int> q;
    h[0] = 0;
    vis[0] = 1;
    q.push(0);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i;i=a[i].next)
        {
            int v = a[i].v, w = a[i].w;
            if(h[v]>h[u]+w)
            {
                h[v] = h[u] + w;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                    cnt[v]++;
                    if(cnt[v]>n)
                        return false;
                }
            }
        }
    }
    return true;
}
void dijkstra(int s)
{
    priority_queue<pll, vector<pll>, greater<pll>> q;
    for (int i = 1; i <= n;i++)
        dis[i] = inf;
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    q.push({0, s});
    while(q.size())
    {
        pll t = q.top();
        q.pop();
        int u = t.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i;i=a[i].next)
        {
            int v = a[i].v;
            if(dis[v]>dis[u]+a[i].w)
            {
                dis[v] = dis[u] + a[i].w;
                q.push({dis[v], v});
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n;i++)
        add(0, i, 0);
    if(!spfa())
    {
        cout << "-1" << endl;
        return 0;
    }
    for (int u = 1; u <= n;u++)
        for (int i = head[u]; i;i=a[i].next)
            a[i].w += h[u] - h[a[i].v];
    for (int i = 1; i <= n;i++)
    {
        dijkstra(i);
        int ans = 0;
        for (int j = 1; j <= n;j++)
        {
            if(dis[j]==inf)
                ans += j * inf;
            else
                ans += j * (dis[j] + h[j] - h[i]);
        }
        cout << ans << endl;
    }
}