无负环全源最短路最直接的算法是 floyd，复杂度 \(O(V^3)\)。
还有一种 Johnson 算法。复杂度为 \(O(VElogV)\)，在图非常稀疏的时候有用。
Johnson先对边权进行调整，使得所有边的边权都为正，这样就可以跑 dijkstra 了。
一个朴素的做法是所有边都加上一个值，但是这样经过的边越多，权值越大，显然不合适。
Johnson 的思想是在走到一个点的时候扣除一个权值，在走出一个点的时候加上一个权值，这样无论经过多少个点，中间结点经历一进一出、权值一减一增会全部抵消。最终实际权值只需要用起点和终点进行调整。
关键是如何合理设计权值，使得调整后的边权全部为正。
如果有一条边 \(e_{u \rightarrow v}\) 的权值为负，我们需要将其调到至少为零，即调增 \(|w_{uv}|\)。
如果从 \(u \rightarrow v\) 负权的边有多条，那么调增量至少为绝对值最大那个。单纯考虑这两个点确实就是可行的了。但是如果考虑整体，可能有另外一条中转道路使得 \(u \rightarrow v\) 的权值还是很低。所以这个其实启发我们求出所有点对之间的最短路，以这个最短路的结果作为依据来调整。
Johnson 的做法是设置一个辅助起点，向每个点连一个边权为 \(0\) 的边，先做一遍 spfa，求出各个点到这个辅助起点的距离。
此时只需根据求得的距离对边权进行调整：
设原边权为 \(w_{uv}\)，调整后的边权为 \(w_{uv}+h_u-h_v\)。
这样一定是把所有边的权重都修正为非负的。
简单证明，对于一条边 \(e_{u \rightarrow v}\)，在原图中，最短路跑完后一定有 \(h_v \le h_u+w_{uv}\)，移项后 \(w_{uv}+h_u-h_v \ge 0\)。
在新图中求完最短路后，\(dis_{uv}'=dis_{uv}+h_u-h_v\)。
只需要按起点和终点的权重进行调整即可。
无负边权的最短路可以用 dijkstra 计算，每个顶点作为起点跑一次，每次复杂度 \(O(ElogV)\)， 复杂度 \(O(VElogV)\)。
deque<int> q;for (int i = 1; i <= n; i++) q.push_back(i), in[i] = true;fill(in + 1, in + n + 1, true);while (!q.empty()) {int now = q.front();q.pop_front(), in[now] = false;for (auto [nxt, len] : g[now])if (dis[nxt] > dis[now] + len) {dis[nxt] = dis[now] + len;cnt[nxt] = cnt[now] + 1;if (cnt[nxt] >= n) {cout << "-1\n";return;}if (!in[nxt]) {in[nxt] = true;if (q.empty() || dis[nxt] < dis[q.front()])q.push_front(nxt);elseq.push_back(nxt);}}}for (int i = 1; i <= n; i++)for (auto [nxt, len] : g[i]) gg[i].emplace_back(nxt, len + dis[i] - dis[nxt]);priority_queue<pii, vector<pii>, greater<>> pq;for (int i = 1; i <= n; i++) {pq.emplace(0, i), fill(dis2, dis2 + n + 1, inf);while (!pq.empty()) {auto [len, now] = pq.top();pq.pop();if (dis2[now] != inf) continue;dis2[now] = len;for (auto [nxt, len2] : gg[now]) pq.emplace(len + len2, nxt);}ll ans = 0;for (ll j = 1; j <= n; j++) {if (dis2[j] == inf)ans += j * inf;elseans += j * (dis2[j] - dis[i] + dis[j]);}cout << ans << '\n';}