Help me pls with edmond algorithm

As formatted using code tags etc:

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
63
64
65
66
67
68
69
70
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;

#define V 6

bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
	bool visited[V];
	memset(visited, 0, sizeof(visited));

	queue <int> q;

	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	// Standard BFS Loop
	while (!q.empty())
	{
		int u = q.front();

		q.pop();

		for (int v = 0; v < V; 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[V][V], int s, int t)
{
	int u, v;
	int rGraph[V][V];

	for (u = 0; u < V; u++)
		for (v = 0; v < V; v++)
			rGraph[u][v] = graph[u][v];

	int parent[V];
	int max_flow = 0;

	while (bfs(rGraph, s, t, parent))
	{
		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;
}


Note L56, 62, 63 - path_flow has not been defined, so the program does not compile.

Last edited on
https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

The variable you need is defined in the above link.
For further studies, here's a helpful video;
https://www.youtube.com/watch?v=OViaWp9Q-Oc

It is briefly discussed in "Introduction to Algorithms" by CLRS. (Page 727 in the third edition), in which bfs and Ford Fulkerson algorithms are also explained.
Last edited on
Topic archived. No new replies allowed.