修改Java福特福尔克森的实现，以打印在最大流量解决方案的每一个边缘使用的最大流量？

Question

我想修改Ford-Fulkerson算法的这个实现（也发布在下面），这样我就可以绘制节点图并分析数据。我不仅要输出最大流，而且要输出每个边的最大流，例如，如果最大流是50，并且它使用了从节点1到3的值为10的流，我想以1-3-10或类似的格式打印它。我试过打印u和v,然后打印剩余的[u][v],但看起来不对。有什么想法吗？

// 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 = 6; //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 
    { 
        // Let us create a graph shown in the above example 
        int graph[][] =new int[][] { {0, 16, 13, 0, 0, 0}, 
                                    {0, 0, 10, 12, 0, 0}, 
                                    {0, 4, 0, 0, 14, 0}, 
                                    {0, 0, 9, 0, 0, 20}, 
                                    {0, 0, 0, 7, 0, 4}, 
                                    {0, 0, 0, 0, 0, 0} 
                                }; 
        MaxFlow m = new MaxFlow(); 

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

    } 
} 

Answer 1

每当您沿着增大路径流动时，您就会用流动值增加rgraph中的每个边（并用相同的值减小其反向）。由于rgraph被初始化为graph的值，这意味着您可以通过取graph[u][v]-rgraph[u][v]中的正条目来获得您想要的东西。对于您的示例，结果是

0 12 11 0 0 0
-12 0 0 12 0 0
-11 0 0 0 11 0
0 -12 0 0 -7 19
0 0 -11 7 0 4
0 0 0 -19 -4 0

这与CLRS图中的结果相匹配。第26.6页。727，在此示例似乎有其起源。