1

我需要修改最大流量算法，以便我可以查看与最大流量相关的路径。无需打印与图相关的所有节点我想打印具有相应容量的图的最大流量的路径。

例如：- 它应该看起来像这样，

**

0-1 = capacity1
1-3 = capacity2
3-5 = capacity3

** 因此，通过添加容量可以验证最大流量，因为两个值相同。

请帮我解决这个问题，在此先感谢。

公共类 MaxFlow_Ford_Fulkerson {

static class Graph {
int vertices;
int graph[][];

public Graph(int vertex, int[][] graph) {
    this.vertices = vertex;
    this.graph = graph;
}

public int findMaxFlow(int source, int sink) {

    int[][] residualGraph = new int[vertices][vertices];


    for (int i = 0; i <vertices ; i++) {
        for (int j = 0; j <vertices ; j++) {
            residualGraph[i][j] = graph[i][j];
        }
    }


    int [] parent = new int[vertices];

    int max_flow = 0; 

    while(isPathExist_BFS(residualGraph, source, sink, parent)){
        int flow_capacity = Integer.MAX_VALUE;

        int t = sink;
        while(t!=source){
            int s = parent[t];
            flow_capacity = Math.min(flow_capacity, residualGraph[s][t]);
            t = s;
        }

        t = sink;
        while(t!=source){
            int s = parent[t];
            residualGraph[s][t]-=flow_capacity;
            residualGraph[t][s]+=flow_capacity;
            t = s;
        }

        max_flow+=flow_capacity;
    }
    return max_flow;
}

public boolean isPathExist_BFS(int [][] residualGraph, int src, int dest, int [] parent){
    boolean pathFound = false;

    boolean [] visited = new boolean[vertices];

    Queue<Integer> queue = new LinkedList<>();

    queue.add(src);
    parent[src] = -1;
    visited[src] = true;

    while(queue.isEmpty()==false){
        int u = queue.poll();

        for (int v = 0; v <vertices ; v++) {
            if(visited[v]==false && residualGraph[u][v]>0) {
                queue.add(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    pathFound = visited[dest];
    return pathFound;
}}*

** *

public static void main(String[] args) {
    int vertices = 6;
    int graph[][] = { {0, 10, 8, 0, 0, 0},
            {0, 0, 5, 5, 0, 0},
            {0, 4, 0, 0, 10, 0},
            {0, 0, 9, 0, 10, 3},
            {0, 0, 0, 6, 0, 14},
            {0, 0, 0, 0, 0, 0}
    };
    Graph g = new Graph(vertices, graph);
    int source = 0;
    int destination = 5;
    int max_flow = g.findMaxFlow(source,destination);
    System.out.println("Maximum flow : " max_flow); }}

* **

4

0 回答 0