Help me pls with edmond algorithm

Jun 12, 2021 at 4:20pm
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 Jun 12, 2021 at 4:21pm
Jun 15, 2021 at 6:36am
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 Jun 15, 2021 at 8:49pm
Topic archived. No new replies allowed.