java - 修改 Java Ford Fulkerson 实现以打印最大流量解决方案中每个边缘使用的最大流量？

Question

我想修改this implementation of the Ford-Fulkerson algorithm (也在下面发布)以便我可以绘制节点图并分析数据。我不仅想输出最大流量，还想输出每个边缘的最大流量，例如，如果最大流量为 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，p. 中的结果相匹配。 727，这个例子似乎起源于此。