关于SPFA判负环
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/2/9 08:20
  • 上次更新2023/10/28 09:21:10
查看原帖
关于SPFA判负环
439327
南瓜桐楼主2022/2/9 08:20

因此如果需要判断整个图上是否存在负环,最严谨的做法是建立一个超级源点,向图上每个节点连一条权值为 0 的边,然后以超级源点为起点执行 Bellman-Ford 算法。 ---OI Wiki

那我在求最短路径时,是不是需要用两次SPFA,一次一s为起点求最短路,一次一超级原点为起点求是否存在负环QAQ

2022/2/9 08:20
加载中...