关于 Johnson 最短路径算法的一些疑惑
  • 板块灌水区
  • 楼主distant_skys
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/30 13:59
  • 上次更新2023/11/4 08:33:31
查看原帖
关于 Johnson 最短路径算法的一些疑惑
392380
distant_skys楼主2021/8/30 13:59

在 OI-Wiki 中有一段话不懂:

我们新建一个虚拟节点(在这里我们就设它的编号为 00 )。从这个点向其他所有点连一条边权为 00 的边。

接下来用 Bellman-Ford 算法求出从 00 号点到其他所有点的最短路,记为 hih_i

已经建立了一个点,与每个节点的距离为 0 ,那么除了遇到负环,是不是这个节点与其他节点的最短路预处理之后还是为 0 ?

这个理解对吗?

2021/8/30 13:59
加载中...