Johnson 全源最短路
特点
- 可求图上任意两点间的最短路，比Floyd快
- 支持负权图，且可判断负环
核心流程
- 创建超级源点0，并以0为起点向图中各结点建边，边权均为0.
- 以0为起点进行SPFA，求出节点0到各节点\(i\)的最短路，记为\(h[i]\)。由于SPFA的自身特点，这一步可以同时判断负环。
- 更新图上原来所有边的边权\(w_i\)，
w[i]+=h[u]-h[v]，其中\(u,v\)是边\(i\)的起点和终点。
- 枚举图上所有点为起点进行Dijskra，求出图上任意两点\(u,v\)间的最短路\(d[u][v]\)。
- 更新\(d[u][v]\)，即减去之前加上的边权，
d[u][v]-=h[u]-h[v]
- 最后所得的\(d[u][v]\)即最终答案。
Johnson 全源最短路
原文：https://www.cnblogs.com/streamazure/p/13784101.html
