缺少埃德蒙茲卡普最大流算法一些路徑

Question

我實現Edmond Karp algorithm，但似乎這不是正確的，我沒有得到正確的流量，可以考慮下面的圖像和流4〜8：

算法運行如下：

首先發現4→1→8， 然後發現4→5→8 後4→1→6→8

而且我覺得第三條道路是錯誤的，因爲通過使用這條道路，我們不能使用從6→8流（因爲它使用），而事實上，我們不能用4→5→6→8流。

事實上，如果我們選擇4→5→6→8，然後4→1→3→7→8，然後4→1→3→7→8我們可以獲得更好的流動（40）。

我實現了從維基示例代碼算法。我認爲我們不能使用任何有效的路徑，事實上這種貪婪的選擇是錯誤的。

我錯了嗎？

代碼是如下面（在C＃，閾值是0，並且不影響算法）：

public decimal EdmondKarps(decimal[][] capacities/*Capacity matrix*/, 
        List<int>[] neighbors/*Neighbour lists*/, 
        int s /*source*/, 
        int t/*sink*/, 
        decimal threshold, 
        out decimal[][] flowMatrix 
        /*flowMatrix (A matrix giving a legal flowMatrix with the maximum value)*/ 
        ) 
    { 
     THRESHOLD = threshold; 
     int n = capacities.Length; 
     decimal flow = 0m; // (Initial flowMatrix is zero) 
     flowMatrix = new decimal[n][]; //array(1..n, 1..n) (Residual capacity from u to v is capacities[u,v] - flowMatrix[u,v]) 
     for (int i = 0; i < n; i++) 
     { 
      flowMatrix[i] = new decimal[n]; 
     } 

     while (true) 
     { 
      var path = new int[n]; 
      var pathCapacity = BreadthFirstSearch(capacities, neighbors, s, t, flowMatrix, out path); 
      if (pathCapacity <= threshold) 
       break; 
      flow += pathCapacity; 

      //(Backtrack search, and update flowMatrix) 
      var v = t; 
      while (v != s) 
      { 
       var u = path[v]; 
       flowMatrix[u][v] = flowMatrix[u][v] + pathCapacity; 
       flowMatrix[v][u] = flowMatrix[v][u] - pathCapacity; 
       v = u; 
      } 
     } 
     return flow; 
    } 

    private decimal BreadthFirstSearch(decimal[][] capacities, List<int>[] neighbors, int s, int t, decimal[][] flowMatrix, out int[] path) 
    { 
     var n = capacities.Length; 
     path = Enumerable.Range(0, n).Select(x => -1).ToArray();//array(1..n) 
     path[s] = -2; 
     var pathFlow = new decimal[n]; 
     pathFlow[s] = Decimal.MaxValue; // INFINT 
     var Q = new Queue<int>(); // Q is exactly Queue :) 
     Q.Enqueue(s); 
     while (Q.Count > 0) 
     { 
      var u = Q.Dequeue(); 
      for (int i = 0; i < neighbors[u].Count; i++) 
      { 
       var v = neighbors[u][i]; 
       //(If there is available capacity, and v is not seen before in search) 
       if (capacities[u][v] - flowMatrix[u][v] > THRESHOLD && path[v] == -1) 
       { 
        // save path: 
        path[v] = u; 
        pathFlow[v] = Math.Min(pathFlow[u], capacities[u][v] - flowMatrix[u][v]); 
        if (v != t) 
         Q.Enqueue(v); 
        else 
         return pathFlow[t]; 
       } 
      } 
     } 
     return 0; 
    } 

Answer 1

選擇路徑的方式是不重要的。

你必須按相反的順序與路徑容量添加路徑的邊緣，並減少該值的路徑的邊緣的能力。

其實這個解決方案的工作原理：

while there is a path with positive capacity from source to sink{ 
    find any path with positive capacity from source to sink, named P with capacity C. 
    add C to maximum_flow_value. 
    reduce C from capacity of edges of P. 
    add C to capacity of edges of reverse_P. 
} 

最後最大流量值是在循環C小號總和。

如果您想要查看您所做的最大流量中的邊界流量，可以在某處保留初始圖表，邊緣e中的流量應爲original_capacity_e - current_capacity_e。