Sedgewick和Wayne的Bellman ford基于队列的方法-算法，第4版

1. 你是对的。在其在线资料中，作者解释说，他们检查每个Vth调用以分摊构建相关的边缘加权有向图并在其中找到周期的成本：

因此，为了实现negativeCycle（），BellmanFordSP.java从e​​dgeTo
[]的边缘构建了一个边缘加权的有向图，并在该有向图中寻找一个循环。为了找到循环，它使用EdgeWeightedDirectedCycle.java（第4.3节中DirectedCycle.java的一个版本），适用于边缘加权有向图。
我们仅在每次Vth调用Relax（）之后才执行此检查，从而摊销此检查的费用 。

换句话说，您可以更频繁地检查，但是这样会冒着性能损失的风险。

1. 同样，你是对的。当前

   while

   在构造函数中循环检查是否存在负循环。但是，在最坏的情况下，该

   relax

   方法可以通过检查循环中的第一个边沿来检测

   for

   循环，而不是退出循环将继续并检查其他边沿（最多

   V-2

   ）。通过建议的改进可以节省大量时间。