为什么Bellman-Ford不能用于单源最长路径？

Question

Dijkstra不能用于最长路径，因为它使用了当前最短路径肯定比其他路径短的属性。当然，假设没有负边权重，这是正确的。这也是为什么最长路径在Dijkstra上不起作用的原因，因为当前的最长路径不能保证以后不会有另一条更长的路径采用更大的值。

另一方面，贝尔曼福特提供了负重的灵活性，但性能较差。这意味着对于贝尔曼·福特来说，它不会像Dijkstra那样贪婪。这就是为什么我感到困惑的原因--为什么Bellman Ford不能用于单源最长路径问题(NP hard)？例如，我们可以简单地将图的所有权重乘以-1，并找到最短路径，这将是原始图的最长路径。

Answer 1

贝尔曼-福特允许重复使用圆弧(否则，即使在存在负循环的情况下，也会有定义良好的最短路径)，而单源最长路径问题的NP难度来自于它不是这样的事实(否则，您可以在将所有权重乘以−1之后使用贝尔曼-福特)。