Stack Overflow
Stack Overflow

Questions tagged [edmonds-karp]

The Edmonds-Karp algorithm is a polynomial-time algorithm for finding the maximum flow in a flow network.

37 questions
10
votes
1 answer

Edmonds-Karp Algorithm for a graph which has nodes with flow capacities

I am implementing this algorithm for a directed graph. But the interesting thing about this graph nodes have also their own flow capacities. I think, this subtle change of the original problem must be handled in a special way. Because, In original…
bfaskiplar
  • 865
  • 1
  • 7
  • 23
9
votes
3 answers

How to get the cut-set using the Edmonds–Karp algorithm?

I implemented the Edmonds–Karp algorithm using the Pseudocode that I found in the Edmonds–Karp algorithm wiki page: http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm It works great, yet the algorithm output is the max flow value(min cut…
ciochPep
  • 2,472
  • 4
  • 26
  • 30
8
votes
2 answers

Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?

I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently: Instead of going through all edges in residual graph, I only went through the edges that are present in the original graph, using the adjacency…
xyz
  • 3,349
  • 1
  • 23
  • 29
5
votes
1 answer

Max flow in unweighted graph

Max flow problem is usually solved by edmond-karp algorithm, which is building residual graph, and using BFS to find augmenting paths. But usually max flow problem is defined for weighted graph. For unweighted graph, we can simply treat the weight…
Justin Li
  • 1,035
  • 2
  • 12
  • 19
4
votes
2 answers

Update Maximum Flow After Adding an Edge

Consider we have a network flow and using Edmond-Karp algorithm, we already have the maximum flow on the network. Now, if we add an arbitrary edge (with certain capacity) to the network, what is the best way to update the maximum flow? I was…
Nima
  • 276
  • 3
  • 15
3
votes
1 answer

Boost max flow algorithms do not compile. error: forming reference to void

Boost provides three different algorithms for finding max flow in directed graphs: boykov_kolmogorov, edmonds_karp and push_relabel. All of them have named and non-named parameter versions. Parameter sets they use are also very similar. Despite…
Nikita Rudenko
  • 55
  • 1
  • 5
3
votes
0 answers

Why is the complexity of Edmonds-Karp algorithm lesser than Ford-Fulkerson's?

The ford fulkerson complexity is O(FE), but the edmond karps is O(VE^2). This is based on the premise that every edge can only be critical O(V) number of times, and this applies to all the edge so we have O(VE) number of times possible that an edge…
oldselflearner1959
  • 633
  • 1
  • 5
  • 22
3
votes
1 answer

C implementation of an algorithm for flow resolution with non-weighted, bidirectional edges, and nodes with flow capacity

I have tried looking in stack overflow for an answer to my question. I've found those answers, but their solution doesn't really apply to my case, as I have non-directed edges. I cannot create a new vertex with edges going in at Vin and edges goint…
chbp
  • 301
  • 2
  • 10
3
votes
1 answer

Using Named parameters and Bundled properties with edmonds_karp_max_flow()

I am trying to use Named parameters with Bundled properties in the edmonds_karp_max_flow algorithm of the Boost-graph library. To show my problem, I took the existing edmonds-karp example and turned the Internal properties into Bundled properties (I…
maelvls
  • 78
  • 12
3
votes
1 answer

Max Flow Linear time algorithm, Find a valid flow

So let me explain the question: You are given a graph. You find the max flow. But it turns out that an edge, e_i, had the wrong capacity. It had one less. Unfortunately, the flow was maxed out at the old capacity. Compute the new max flow in linear…
user678392
  • 1,981
  • 3
  • 28
  • 50
2
votes
1 answer

Missing some paths in edmonds karp max flow algorithm

I'd implement Edmond Karp algorithm, but seems it's not correct and I'm not getting correct flow, consider following graph and flow from 4 to 8: Algorithm runs as follow: First finds 4→1→8, Then finds 4→5→8 after that 4→1→6→8 And I think third…
Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
2
votes
0 answers

Implementation using Edmond-Karp's algorithm not outputing the maximum flow value

I am implementing a program to solve a matching problem by using the reduction from a matching problem to a maximum flow problem, which I am determined to solve using Edmond-Karp's algorithm. I have looked through and taken impressions from…
lolol
  • 21
  • 2
1
vote
1 answer

How to define cut set with Edmonds Karp Impl?

I'm using JGraphT, and I'm using EdmondsKarpMFImpl. The question is: How to define the whole set of edges what is 'participate' in min-cut. I tried to use the getCutEdges method, but it only returns 1 edge. I have the following graph: (all the…
Gábor Szegedi
  • 37
  • 5
1
vote
1 answer

Efficient, max-flow algorithm to route as many people as possible to one location?

I am trying to determine an efficient, maximum flow algorithm using a directed graph where, given a list of n flights (where each entry has the starting city, ending city, departure time, arrival time, and capacity of the flight), will route as many…
honethecode265
  • 11
  • 2
1
vote
0 answers

An O(n * log(n)) algorithm for maximum st-flow in a directed planar graph (Borradaile, Klein)

Could someone explain to me using an example how Borradaile-Klein's algorithm for maximum flow works? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6392&rep=rep1&type=pdf There are a lot of Ford-Fulkerson's examples…
Pawel_DM
  • 31
  • 3
1
2 3