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 ( n m l o g n ) O(nmlogn) O(nmlogn)其中n为结点个数，m为边的个数。
代码：LuoguP5905
原文地址：https://blog.csdn.net/qq_45523675/article/details/136213367
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！