我目前正在研究 Bellman-Ford 算法，突然出现了一个疑问。据我所知，Bellman-Ford 算法从其源中创建最短路径，如果图中可能存在负回圈，它回传 true 并且算法停止，另一方面，它回传 false 并回传最短路径。

我现在的问题是，该算法是否避免了图中的正回圈以创建最短路径，还是只是不考虑它们（因此落入陷阱）？

提前致谢！

uj5u.com热心网友回复：

如果存在负回圈，则没有“最短”路径，因为您可以随心所欲地围绕回圈进行多次，以使路径“更短”（即边缘权重的总和更低）。如果图有负回圈，那么算法可能会因陷入无限回圈或回传不是最短的路径而失败；因此，我们对能够“检测”负回圈并且不会以其中一种方式失败的算法感兴趣。

Bellman-Ford 就是这种算法的一个例子：如果图有一个负回圈，那么 Bellman-Ford 算法检测到没有最短路径（并且可以报告负回圈是什么）。这意味着该算法正确地确定了寻找最短路径的问题对该输入没有定义的解决方案，而不是给出错误的结果或未能终止。

正回圈不会产生任何类似的问题，因为正回圈的存在并不意味着没有最短路径。任意多次绕正回圈的解决方案会导致更长的路径（即更高的边权重总和），而不是更短的路径。所以每个最短路径算法都必须正确处理这种情况，包括 Bellman-Ford。

uj5u.com热心网友回复：

考虑一个包含正权重的回圈 <a,b,c,a>。很明显，如果我们将源到顶点a的最短距离设定为边c到a，那么这将与最短路径的最优子结构和Belman-Ford算法的正确性相矛盾。因此该算法评估正回圈的长度，但不将其视为最短路径。