Ford-Fulkerson algorithm with depth first search

Question

I am doing a homework of Implementing Ford-Fulkerson algorithm, they said we should use DFS for path finding but i am stuck at somewhere. I am not posting the code because it's localized too much. Actually my DFS algorithm works well but the dead ends cause a problem for example if i run my code i get output of DFS like that

0=>1 1=>2 1=>3 3=>5

It starts from 0 and it ends in 5 but the 1=>2 part is unnessecary for my algorithm also i store my path using [N][2] matrix. My question is how can I remove the dead ends in my resulting matrix (Inside of the DFS recursion perhaps?)

Answer 1

You should perform the DFS to find some path between the source and the sink. Then, when the dfs is retuning, you should add a flow

Here's an example. The function "send" is a DFS. Notice that I pass along with the DFS the minimum capacity value found during the search:

https://github.com/juanplopes/icpc/blob/master/uva/820.cpp

int send(int s, int t, int minn) {
    V[s] = true;

    if (s==t) return minn;

    for(int i=1; i<=n; i++) {
        int capacity = G[s][i]-F[s][i];
        if (!V[i] && capacity > 0) {
            if (int sent = send(i, t, min(minn, capacity))) {
                F[s][i] += sent;
                F[i][s] -= sent;
                return sent;
            }
        }
    }

    return 0;
}