Edmond Karp Algorithm / Network Flow

#1

I used a similar code as given in the algorithm to find the maximum flow of the Network graph.

In this, for testcase
1
6 10
1 6 9
3 2 7
6 1 7
5 1 2
5 3 2
5 4 5
3 2 8
2 2 8
3 5 9
2 3 3

It is giving the output as 9.
but the correct ans is 16.
I’m not able to find the mistake, please help.
Thank you.

#2

hello @adarsh_2001
r u submitting it anywhere?

#3

crosscheck ur implementation with this->

int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;

int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(n);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}

source -> link

#4

Yes, I’m submitting it here.
https://practice.geeksforgeeks.org/problems/find-the-maximum-flow/0#
kindly run it from here.
https://practice.geeksforgeeks.org/viewSol.php?subId=eecf0e54301fd8549410768dee7a3757&pid=1920&user=2001adarshsingh
This is my solution, for the problem.
Please check.

#5

ok pls wait i m checking , it might take some time

#6

@adarsh_2001
ur implementation is correct.
dont know why it is giving wrong result. check their implementation

#7

Okay thank You, @aman212yadav

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.