C++ Program to Implement The Edmonds-Karp Algorithm

Code:

#include    cstdio
#include    cstdio
#include    queue
#include    cstring
#include    vector
#include    iostream
#include    conio.h

using namespace std; 

int capacities[10][10];
int flowPassed[10][10];
vector graph[10];
int parentsList[10];       
int currentPathCapacity[10];  

int bfs(int startNode, int endNode)
{
    memset(parentsList, -1, sizeof(parentsList));
    memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

    queue q;
    q.push(startNode);

    parentsList[startNode] = -2;
    currentPathCapacity[startNode] = 999;

    while(!q.empty())
    {
        int currentNode = q.front();
        q.pop();

        for(int i=0; i
        {
            int to = graph[currentNode][i];
            if(parentsList[to] == -1)
            {
                if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
                {
                    parentsList[to] = currentNode;
                    currentPathCapacity[to] = min(currentPathCapacity[currentNode], 
                    capacities[currentNode][to] - flowPassed[currentNode][to]);
                    if(to == endNode)
                    {
                        return currentPathCapacity[endNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}

int edmondsKarp(int startNode, int endNode)
{
    int maxFlow = 0;
      while(true)
    {
        int flow = bfs(startNode, endNode);
        if (flow == 0) 
        {
            break;
        }
        maxFlow += flow;
        int currentNode = endNode;
        while(currentNode != startNode)
        {
            int previousNode = parentsList[currentNode];
            flowPassed[previousNode][currentNode] += flow;
            flowPassed[currentNode][previousNode] -= flow;
            currentNode = previousNode;
        }
    }
    return maxFlow;
}
int main()
{
    int nodesCount, edgesCount;
    cout<<"enter the number of nodes and edges\n";
    cin>>nodesCount>>edgesCount;

    int source, sink;
    cout<<"enter the source and sink\n";
    cin>>source>>sink;

    for(int edge = 0; edge < edgesCount; edge++)
    {
        cout<<"enter the start and end vertex alongwith capacity\n";
        int from, to, capacity;
        cin>>from>>to>>capacity;

        capacities[from][to] = capacity;
        graph[from].push_back(to);

        graph[to].push_back(from);
    }

    int maxFlow = edmondsKarp(source, sink);

    cout<

    getch();
}


Output:

enter the number of nodes and edges
6
10
enter the source and sink
0
5
enter the start and end vertex alongwith capacity
0
1
16
enter the start and end vertex alongwith capacity
0
2
13
enter the start and end vertex alongwith capacity
1
2
10
enter the start and end vertex alongwith capacity
2
1
4
enter the start and end vertex alongwith capacity
1
3
12
enter the start and end vertex alongwith capacity
3
2
9
enter the start and end vertex alongwith capacity
2
4
14
enter the start and end vertex alongwith capacity
4
3
7
enter the start and end vertex alongwith capacity
4
5
4
enter the start and end vertex alongwith capacity
3
5
20


Max Flow is:23


More C++ Programs: