포드 - Fulkerson에 출력 경로는 다음

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)); 

     } 
    } 

. 찍은 경로를 알고 싶습니다. 그래서 그래픽으로 진행되는 것을 볼 수 있습니다.

편집 : 누군가가 지적한 바와 같이 오류는 매트릭스를 만들 때 두 개의 요소가 누락되었다는 것입니다. 사용 된 경로를 출력하는 방법을 여전히 확신 할 수 없습니다.

Answer 1

ArrayIndexOutOfBoundsException은 잘못된 색인에서 배열에 액세스 할 때 발생합니다. 액세스

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

시도 및 rgraph 8 일 차원 배열 8 개 인덱스. 그러나 라인 # 113에서 {0, 0, 14, 0, 8, 0, 20},은 7 개의 요소를 가지며, 이는 의 6 번째 1 차원 배열입니다. 따라서 그래프 [5] [7]에 액세스하면 범위를 벗어나는 오류가 발생합니다.