algorithm - 为什么 Bellman-Ford 不能用于单源最长路径？
问题描述
Dijkstra 不能用于最长路径，因为它使用当前最短路径肯定比其他路径之一短的属性。当然，这是正确的，假设没有负边权重。这个概念也是最长路径在 Dijkstra 上不起作用的原因，因为当前最长的路径并不能保证以后不会有另一条更长的路径采用更大的值。
另一方面，Bellman Ford 以较差的性能提供了负权重的灵活性。这意味着对于贝尔曼福特来说，它不适用于与 Dijkstra 相同的贪婪属性。所以这就是为什么我很困惑 - 为什么贝尔曼福特不能用于单源最长路径问题（NP 难）？例如，我们可以简单地将图的所有权重乘以 -1 并找到最短路径，这将是原始图的最长路径。
解决方案
Bellman-Ford 允许重复使用弧（否则即使在存在负循环的情况下也会有明确定义的最短路径），而单源最长路径问题的 NP-hardness 源于它没有的事实（否则你可以只需将所有权重乘以 -1 后使用 Bellman-Ford）。