Created
August 24, 2012 19:51
-
-
Save irpap/3454980 to your computer and use it in GitHub Desktop.
Ford Fulkerson
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int fordFulkerson(int n, int s, int t) { | |
| //ASSUMES: cap[u][v] stores capacity of edge (u,v). cap[u][v] = 0 for no edge. | |
| //Initialise the flow network so that fnet[u][v] = 0 for all u,v | |
| int flow = 0; //no flow yet | |
| while (true) { | |
| //Find an augmenting path using BFS | |
| int[] prev = new int[n]; | |
| Arrays.fill(prev, -1); | |
| LinkedList<Integer> queue = new LinkedList<Integer>(); | |
| prev[s] = -2; | |
| queue.add(s); | |
| while (!queue.isEmpty() && prev[t] == -1) { | |
| int u = queue.poll(); | |
| for (int v = 0; v < n; v++) { | |
| if (prev[v] == -1) { //not seen yet | |
| if (fnet[v][u] > 0 || fnet[u][v] < cap[u][v]) { | |
| prev[v] = u; | |
| queue.add(v); | |
| } | |
| } | |
| } | |
| } | |
| //See if we couldn't find any path to t (t has no parents) | |
| if (prev[t] == -1) break; | |
| //Get the bottleneck capacity; | |
| int bot = Integer.MAX_VALUE; | |
| for (int v = t, u = prev[v]; u >= 0; v = u, u = prev[v]) { | |
| if (fnet[v][u] > 0) //prefer a backward edge over a forward | |
| bot = min(bot, fnet[v][u]); | |
| else //must be a forward edge otherwise | |
| bot = min(bot, cap[u][v] - fnet[u][v]); | |
| } | |
| //update the flow network | |
| for (int v = t, u = prev[v]; u >= 0; v = u, u = prev[v]) { | |
| if (fnet[v][u] > 0) //backward edge -> subtract | |
| fnet[v][u] -= bot; | |
| else //forward edge -> add | |
| fnet[u][v] += bot; | |
| } | |
| //Sent 'bot' amount of flow from s to v, so update the flow | |
| flow += bot; | |
| } | |
| return flow; | |
| } |
Looks good except it would be nice if you labelled n, s, and t.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is actually Edmonds-Karp algorithm since BFS is used to find the augment path.