BellmanFord算法 Johnson算法解决的问题 带负权的稀疏图的全源最短路 算法流程 重新设置的每条边的权重都大于或等于0，跑完Djikstra后得到的全源最短路，记得要还原，即：f(u,v) = d(u,v) - h[u] + h[v] 例题

题目链接：Luogu P5905 【模板】全源最短路（Johnson） 题目描述： 给定一张有向图，求出任意两点之间的最短路。 题解： 使用Johnson算法即可。其思想就是将一个含有负权边的图变成无负权边的图之后，跑n次Dijkstra算法。对于一个没有负环的图，具体地： 建立超级源点，使其到每个结点建立一条权重为0的有向边，通过Bellman-Ford以超级源点为起点计算一次单元