简单来说就是 spfa 与 dijkstra 连用

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

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

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

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

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

一开始的 $Bellman-Ford$ 算法并不是时间上的瓶颈，若使用 $priorit{y}_{q}ueue$ 实现 $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(false), cin.tie(nullptr);
    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;
    }
}