貝爾曼福特隊列爲基礎的方法 - 算法，第4版

Question

我正在研究爲Bellman-Ford algorithm單源最短路徑queue-based辦法從從書算法Robert Sedgewick and Kevin Wayne - Algorithms, 4th edition 源代碼出現在這個環節http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java。

我有兩點是一個疑問，另一個是代碼改進建議。

1. 在上面的方法中，以下是用於放鬆到頂點距離的鬆弛方法的代碼。

   for (DirectedEdge e : G.adj(v)) { 
       int w = e.to(); 
       if (distTo[w] > distTo[v] + e.weight()) { 
        distTo[w] = distTo[v] + e.weight(); 
        edgeTo[w] = e; 
        if (!onQueue[w]) { 
         queue.enqueue(w); 
         onQueue[w] = true; 
        } 
       } 
       if (cost++ % G.V() == 0){ 
        findNegativeCycle(); 
       } 
   } 
   

在以下條件該方法是找到負循環之前使用。

if (cost++ % G.V() == 0){ 
    findNegativeCycle(); 
} 

以上，他們在圖劃分成本由vertices號檢查negative cycle。這可能是因爲 放鬆完成V-1次，如果放鬆運行Vth時間，這意味着它有循環，其中V是頂點的數量。

但我認爲在基於隊列的方法中，他們使用除數來定期檢查循環是否已經發生。在上述條件成立之前或之後，循環可能發生在 。如果循環發生在上述條件成立之後，則算法必須等待直到下一次條件爲 才能檢測到循環，則如果(cost++ % G.V() == 0)爲真，則沒有必要正好發生循環。所以我認爲除數可以是足夠小的數量，以便我們可以在適當的時間間隔後檢查循環。 我是否正確地認爲？

1. 代碼改進建議是findNegativeCycle()方法可用於在發生循環時返回true。從而。這個條件 -

   if (cost++ % G.V() == 0) { findNegativeCycle(); }

能TO-

if (cost++ % G.V() == 0) 
    if(findNegativeCycle()){ 
     return; 
    } 

改變在代碼迴路不斷即使findNegativeCycle()方法找到了一個週期運行。因此，如果發生循環而不是處理for循環的其餘部分，我們可以返回。

請分享您的想法以上2點。 在此先感謝。

Answer 1

1. 你說得對。在他們online materials，作者解釋說，他們檢查每Vth的調用，以分期償還建設相關的邊加權有向圖，並在其中尋找週期的成本：

因此，爲了實現negativeCycle（）BellmanFordSP。 java從e​​dgeTo []中的邊緣構建一個 邊緣加權有向圖，並在該有向圖中查找循環 。要查找循環，它使用 EdgeWeightedDirectedCycle.java，來自 的DirectedCycle.java版本第4節。3，適用於邊緣加權有向圖。 我們通過僅在每個Vth 呼叫放鬆（）之後執行此檢查來攤銷此支票的成本 。

換句話說，您可以更頻繁地檢查，但那麼您可能會損失性能。

1. 同樣，你是對的。負循環的存在目前在構造函數的while循環中檢查。但是，在最壞的情況下，relax方法可以通過檢查for循環中的第一條邊來檢測循環，而不是退出它將繼續並檢查其他邊（其中最大爲V-2）。隨着您的建議改進，可以節省大量的時間。

Answer 2

很高興看到Miljen Mikic的解答。這對理解算法非常有幫助。但是，我仍然有另一個問題。在文中，它說：「爲了完成實現，我們需要確保算法在V經過後終止 。實現這一目標的一種方法是明確跟蹤通過。」在這裏，我相信變量「成本」是遍數，但是不應該行

if (cost++ % G.V() == 0) 
    findNegativeCycle(); 

是至少爲外循環？像

private void relax(EdgeWeightedDigraph G, int v) 
    { 
     for (DirectedEdge e : G.adj(v) 
      { 
        int w = e.to(); 
        if (distTo[w] > distTo[v] + e.weight()) 
         { 
          distTo[w] = distTo[v] + e.weight(); 
          edgeTo[w] = e; 
          if (!onQ[w]) 
           { 
             q.enqueue(w); 
             onQ[w] = true; 
           } 
         } 
       } 
     if (cost++ % G.V() == 0) 
       findNegativeCycle(); 
     } 

居然連它的外部for循環，它不是最好的解決方案，因爲每個過程中，有可能是要放寬多個頂點。因此，可以在BellmanFordSP的構造函數中設計得更好，方法是記住每次傳遞期間要放鬆多少個頂點。我對麼？謝謝！