使用貝爾曼福特算法檢測負循環

我知道這是一個伸手可及的距離，但我正在關注Princeton's course on Algorithm。我試圖使用Bellman Ford算法來檢測邊緣加權有向圖中的負循環。使用貝爾曼福特算法檢測負循環

There is a negative cycle reachable from the source if and only if the queue is 
nonempty after the Vth pass through all the edges. Moreover, the subgraph of 
edges in our edgeTo[] array must contain a negative cycle.

完整的代碼實現，請訪問：BellmanFordSP.java和EdgeWeightedDirectedCycle.java。具體來說，我堅持在這一點上：

public class BellmanFordSP 
{ 
    private double[] distTo; // distTo[v] = distance of shortest s->v path 
    private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path 
    private boolean[] onQueue;  // onQueue[v] = is v currently on the queue? 
    private Queue<Integer> queue; // queue of vertices to relax 
    private int cost;    // number of calls to relax() 
    private Iterable<DirectedEdge> cycle;// negative cycle (or null if no such cycle) 

    // Computes a shortest paths tree from s to every other vertex 
    public BellmanFordSP(EdgeWeightedDigraph G, int s) 
    { 
     distTo = new double[G.V()]; 
     edgeTo = new DirectedEdge[G.V()]; 
     onQueue = new boolean[G.V()]; 
     for (int v = 0; v < G.V(); v++) 
      distTo[v] = Double.POSITIVE_INFINITY; 
     distTo[s] = 0.0; 

     // Bellman-Ford algorithm 
     queue = new Queue<Integer>(); 
     queue.enqueue(s); 
     onQueue[s] = true; 
     while (!queue.isEmpty() && !hasNegativeCycle()) 
     { 
      int v = queue.dequeue(); 
      onQueue[v] = false; 
      relax(G, v); 
     } 
    } 

    // relax vertex v and put other endpoints on queue if changed 
    // G.V() gives number of vertices in G 
    // G.adj(v) returns an Iterable of edges emanating from vertex v. 
    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 (!onQueue[w]) 
       { 
        queue.enqueue(w); 
        onQueue[w] = true; 
       } 
      } 
      if (cost++ % G.V() == 0) // <-- what does this check do ? 
       findNegativeCycle(); 
     } 
    } 

    // Is there a negative cycle reachable from the source vertex s? 
    public boolean hasNegativeCycle() 
    { 
     return cycle != null; 
    } 


    // Returns a negative cycle reachable from the source vertex s 
    public Iterable<DirectedEdge> negativeCycle() 
    { 
     return cycle; 
    } 

    // by finding a cycle in predecessor graph 
    private void findNegativeCycle() 
    { 
     int V = edgeTo.length; 
     EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V); 
     for (int v = 0; v < V; v++) 
      if (edgeTo[v] != null) 
       spt.addEdge(edgeTo[v]); 

     EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt); 
     cycle = finder.cycle(); 
    }

這個條件是什麼意思：cost++ % G.V() == 0。爲什麼我們只在這個特定的條件下檢查負循環？

來源

2014-12-29 OneMoreError

通常，Bellman-Ford算法會執行| V | -1步驟的放鬆。如果你想檢測負循環，你必須再次運行放鬆。如果你仍然可以再次放鬆網絡，它的確有一個消極的循環。

這就是這種情況正在檢查，如果這是你呼籲放鬆的時間。

請注意，並不總是鬆弛的邊緣是週期的一部分，它可能是一個邊緣，從週期可以得到。

來源

2014-12-29 17:43:07

您可以查看回答問題，我問在計算器Bellman ford queue based approach from Sedgewick and Wayne - Algorithms, 4th edition

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

這種情況在使用固定時間間隔檢測週期。當條件爲真時，週期不會發生。在這個條件變爲真的情況下，循環可以發生，在這種情況下，它必須等待下一次，直到這個條件cost++ % G.V() == 0對於找到循環爲真。如果使用任何其他數字（接近邊數或頂點的小數）作爲除數而不是頂點數，算法將起作用。除數僅用於定期檢查循環。

來源

2015-04-24 03:42:36 anujprashar

使用貝爾曼福特算法檢測負循環

回答

相關問題