约 10 分钟
若图里存在“总权为负的环”，绕环一圈距离还能变小，最短路就不存在（可无限变小）。Bellman-Ford 里若第 n 轮仍能松弛，说明有负环；SPFA 里若某点入队次数超过 n 次，也判定存在负环。
SPFA 中怎样的迹象说明图里有负环？
登录 后可看答案