Bellman-Ford算法判定负环中的疑问
(维基百科)用Bellman Ford判定负环: 因为负权环可以无限制地降低总花费，如果第n(n为结点数)轮仍能通过松弛操作降低花费，就一定存在负环。
算法 进行n - 1轮松弛操作后(这个为大前提): 如果不含负环，算法就能找到源点到所有结点的最短路。把 “不含负环” 记作p。 就有对于 “任意” 的边e(u，v)，有d[u] + w >= d[v]。 (三角不等式)，把这个命题记作q。 上面的就简记为: p -> q。 判断负环时，用q这个命题来判断，如果非q，那么就非p，即含负环。(也就是说，如果进行第n轮松弛操作时，仍然能更新，就说明存在负环) 我的疑问是，是否有 q -> p。有的话，怎么证。 如果没有“q -> p”，我感觉通过非q来判定是否含有负环在逻辑上有问题，因为也有可能“q成立时，非p成立，”。
展开
收起
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
