Johnson
Johnson全源最短路：负权化正权，最后减去势能差
Johnson全源最短路：负权化正权，最后减去势能差 （1）建虚点0，add(0,i,0),跑st=0的单源最短路hi （2）e[i].w+=g[u]-h[v] Q:为何这样不会得到错误答案？ A：[ 最短路 - OI Wiki ]() （3）O(N^2*logN)跑n次dijk Code: ......
Johnson 全源最短路
Johnson 全源最短路 Johnson 和 Floyd 一样是能求出无负环图上任意两点间最短路径的算法。 引入 求任意两点间的最短路可以通过枚举起点，跑 \(n\) 次 SPFA 来解决，时间复杂度是 \(O(n^2 m)\) 的，也可以用 Floyd 解决，复杂度为 \(O(n^3)\)。 或 ......
Johnson 全源最短路学习笔记
[模板传送门](https://www.luogu.com.cn/problem/P5905) 考虑$n$次用优先队列优化的$dijkstra$，时间复杂度$O(nm \log m)$。 但是因为$dijkstra$是能求边权为正的图 考虑将所有边权转化为正，构造虚拟节点$0$，向所有点连接一条边权 ......
Johnson 全源最短路
全源最短路，换一种说法就是n个单源最短路，可以用n次Bellman-Ford或SPFA，非负边权还可以用Dijkstra，可是有负边权用前两个算法还是慢，如果我们能把负边权映射成非负边权的话，一切就都好办了 这里我们引入一个虚拟结点，它和所有点的初始距离都是0，然后，我们求出来这个结点和其他店的最短 ......