フォード - フルカーソンの出力パスはここ

Question

を使用するコードです：私は出力へのパスと、各辺の重みを、それを変更したいのですが、私はどのようにわからない

// Java program for implementation of Ford Fulkerson algorithm 
    import java.util.*; 
    import java.lang.*; 
    import java.io.*; 
    import java.util.LinkedList; 

    class MaxFlow 
    { 
     static final int V = 8; //Number of vertices in graph 

     /* Returns true if there is a path from source 's' to sink 
      't' in residual graph. Also fills parent[] to store the 
      path */ 
     boolean bfs(int rGraph[][], int s, int t, int parent[]) 
     { 
      // Create a visited array and mark all vertices as not 
      // visited 
      boolean visited[] = new boolean[V]; 
      for(int i=0; i<V; ++i) 
       visited[i]=false; 

      // Create a queue, enqueue source vertex and mark 
      // source vertex as visited 
      LinkedList<Integer> queue = new LinkedList<Integer>(); 
      queue.add(s); 
      visited[s] = true; 
      parent[s]=-1; 

      // Standard BFS Loop 
      while (queue.size()!=0) 
      { 
       int u = queue.poll(); 

       for (int v=0; v<V; v++) 
       { 
        if (visited[v]==false && rGraph[u][v] > 0) 
        { 
         queue.add(v); 
         parent[v] = u; 
         visited[v] = true; 
        } 
       } 
      } 

      // If we reached sink in BFS starting from source, then 
      // return true, else false 
      return (visited[t] == true); 
     } 

     // Returns tne maximum flow from s to t in the given graph 
     int fordFulkerson(int graph[][], int s, int t) 
     { 
      int u, v; 

      // Create a residual graph and fill the residual graph 
      // with given capacities in the original graph as 
      // residual capacities in residual graph 

      // Residual graph where rGraph[i][j] indicates 
      // residual capacity of edge from i to j (if there 
      // is an edge. If rGraph[i][j] is 0, then there is 
      // not) 
      int rGraph[][] = new int[V][V]; 

      for (u = 0; u < V; u++) 
       for (v = 0; v < V; v++) 
        rGraph[u][v] = graph[u][v]; 

      // This array is filled by BFS and to store path 
      int parent[] = new int[V]; 

      int max_flow = 0; // There is no flow initially 

      // Augment the flow while tere is path from source 
      // to sink 
      while (bfs(rGraph, s, t, parent)) 
      { 
       // Find minimum residual capacity of the edhes 
       // along the path filled by BFS. Or we can say 
       // find the maximum flow through the path found. 
       int path_flow = Integer.MAX_VALUE; 
       for (v=t; v!=s; v=parent[v]) 
       { 
        u = parent[v]; 
        path_flow = Math.min(path_flow, rGraph[u][v]); 
       } 

       // update residual capacities of the edges and 
       // reverse edges along the path 
       for (v=t; v != s; v=parent[v]) 
       { 
        u = parent[v]; 
        rGraph[u][v] -= path_flow; 
        rGraph[v][u] += path_flow; 
       } 

       // Add path flow to overall flow 
       max_flow += path_flow; 
      } 

      // Return the overall flow 
      return max_flow; 
     } 

     // Driver program to test above functions 
     public static void main (String[] args) throws java.lang.Exception 
     { 
      int graph[][] =new int[][] { {0, 14, 0, 10, 0, 18, 0, 0}, 
             {0, 0, 18, 0, 14, 0, 0, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 10}, 
             {0, 0, 10, 0, 8, 0, 0, 0}, 
             {0, 0, 14, 0, 8, 0, 20}, 
             {0, 0, 0, 6, 0, 0, 16}, 
             {0, 0, 16, 0, 0, 0, 0, 6}, 
             {0,0,0,0,0,0,0,0}         }; 
      MaxFlow m = new MaxFlow(); 

      System.out.println("The maximum possible flow is " + 
           m.fordFulkerson(graph, 0, 7)); 

     } 
    } 

。私は道を知りたいので、グラフィカルに何が起こっているか見ることができます

編集：誰かが指摘したように、私が行列を作成したときに2つの要素が欠けていたということでした。まだ使用されているパスの出力方法は不明です。

Answer 1

ArrayIndexOutOfBoundsExceptionは、無効なインデックスで配列にアクセスするとスローされます。

for (u = 0; u < V; u++) 
    for (v = 0; v < V; v++) 
     rGraph[u][v] = graph[u][v]; 

とrgraph 8 1次元配列で8つの索引にアクセスしよう。しかし、行番号113では、{0, 0, 14, 0, 8, 0, 20},には7つの要素があり、これはの6番目の1次元配列です。したがって、グラフ[5] [7]にアクセスすると、範囲外のエラーが発生しています。