forked from mazedrupok/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 9
/
ford fulkerson algorithm 1
62 lines (61 loc) · 1.57 KB
/
ford fulkerson algorithm 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
bool bfs(int rGraph[][6], int s, int t, int parent[]) {
bool visited[6];
memset(visited, 0, sizeof(visited));
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < 6; v++) {
if (visited[v] == false && rGraph[u][v] > 0) {
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return (visited[t] == true);
}
int fordFulkerson(int graph[6][6], int s, int t) {
int u, v;
int rGraph[6][6];
for (u = 0; u < 6; u++) {
for (v = 0; v < 6; v++) {
rGraph[u][v] = graph[u][v];
}
}
int parent[6];
int max_flow = 0;
while (bfs(rGraph, s, t, parent)) {
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
int graph[6][6] = { {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}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}