spfa判断负环好理解思路汇总（转载）

作者： 作者的头像   假如有点困 ,  2022-04-14 17:38:21 ,  所有人可见 ,  阅读 177

0


  1. 构造一个虚拟节点 O，单向指向所有的节点，且到所有节点距离为0；
  2. 新图是否有负环等价于原始的图。
    3.dist数组一开始为0,没有违背算法过程，可以理解为根据算法已经从O 更新到了各个节点，接下来的代码就是顺理成章。所以dist数组从所有为0的状态开始是有对应意义的。就是先走一步。

0 评论

1024
x