关于#c++#的问题：在算法SPFA中，数组“cnt”用于判断负环，通常写为“if（cnt[v]>n）”n是图中的顶点编号

Question

在算法SPFA中，数组“cnt”用于判断负环

，通常写为“if（cnt[v]>n）”n是图中的顶点编号。我认为它是否可以写成“if（cnt[v]>=n）”？根据没有负循环的图，单元路径的边数等于顶点数减一（不知道是不是公理）。只是一个小问题。
谢谢大老们

Answer 1

当没有负环时，从任意一个顶点出发到其余所有顶点的单源最短路径的边数不会超过n-1。因此，如果算法运行到某个节点v时，cnt[v]的值已经大于等于n，那么说明从起点到v的路径上必定存在环，且该环中至少包含n条边，即存在负环。

因此，将判断条件从“if(cnt[v]>n)”改为“if(cnt[v]>=n)”是正确的，并不影响算法的正确性。这样修改后，如果存在负环，算法会在第n次松弛操作时就返回true，而不是等到第n+1次松弛操作才返回。