算法设计手册说：
大多数图形算法都不容易适应负数。事实上，最短路径算法在处理负数时会遇到问题，并且使用这种技术当然不会生成可能的最长路径。
但为什么？当我们只是在原始权重前面加上一个负数-时，我认为大多数涉及权重的图形问题都可以平等处理，对吧？
问问题
1727 次
3 回答
7
于 2012-04-30T09:41:58.140 回答
4
事实上，最短路径算法在处理负数时会遇到麻烦，
这对于Dijkstra 的 Algorithm是正确的，但对于一般的最短路径算法则不然。如果图不包含负循环，Bellman-Ford 算法可以处理负边权重。然而：
Bellman-Ford 可以检测负循环并报告它们的存在，但如果无法从源头到达负循环，它就无法产生正确的答案。
于 2012-04-30T09:56:30.877 回答
1
我将专门为最短路径问题添加答案。杰克的回答很好地描述了负边缘的一般问题。
考虑一个图，每条边都有边G = (V, E)长。中的最短路径与中的最长路径相同。已知最长路径问题在一般图中是 NP 难的。尽管它可以在 DAG 和其他类别的图中以线性时间求解。l(e) ≤ 0e ∈ EGG'l'(e) = - l(e) ≥ 0 ∀e ∈ E
正如cls 回答的那样，问题仅在于负循环，Bellman-Ford 算法可以处理一些负边。但是最长路径算法必须处理图中的循环，Bellman-Ford 无法对具有负循环的图给出正确答案。因此，Bellman-Ford 算法只能用于计算没有正循环的图中的最长路径。提到，因为这种想法显然并不少见。
于 2015-01-11T19:51:41.403 回答