Luogu P5905 【模板】全源最短路（Johnson）题解全源最短路 Johnson算法

本文主要是介绍Luogu P5905 【模板】全源最短路（Johnson）题解全源最短路 Johnson算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Luogu P5905 【模板】全源最短路（Johnson）
题目描述：

给定一张有向图，求出任意两点之间的最短路。

题解：

使用Johnson算法即可。其思想就是将一个含有负权边的图变成无负权边的图之后，跑n次Dijkstra算法。对于一个没有负环的图，具体地：

建立超级源点，使其到每个结点建立一条权重为0的有向边，通过Bellman-Ford以超级源点为起点计算一次单元最短路，得到dis[0][i]表示超级源点0到结点i的最短路径；
遍历原图中的每一条边(u, v, w)，修改权重为w + dis[0][u] - dis[0][v]；
依次以每个结点作为起点执行Dijkstra算法，得到dis[i][j]表示以i为起点到j的最短路；
修改dis[i][j]为dis[i][j] - dis[0][i] + dis[0][j]。

通过上述操作后dis[i][j]即表示i到j的最短路。首先解释修改边权后一定不存在负边，在最短路中如果存在(u, v, w)那么一定满足：dis[0][u] + w >= dis[0][v]，因此有：w + dis[0][u] - dis[0][v] >= 0这也就表明修改后的每条边权值均为正。不难发现若两个结点s和t之间的最短路依次经过e1, e2, ..., en，那么最终的值为w1 + w2 + ... + wn + dis[0][s] - dis[0][t]，因此只需要在最后减去多加的一部分即可获得最终的最短路。
上述算法的时间复杂度为 $O (nm l o g n)$ 其中n为结点个数，m为边的个数。