Why Edmonds-Karp Shortest Augmenting Path Has Cubic Time

Question

It was given that Edmonds-Karp algorithm bound has cubic running time if it uses the shortest flow-augmenting path:

$|E(G)| \times (|V(G)|+1)/2$

$|E(G)|$ is quadratic in terms in $|V(G)|$, why? For each edge, we have 2 vertices, so for $n$ edges, we have $2n$ not quadratic, is not it?

Second, could you please tell me what is the shortest flow-augmenting path here that we should use in Edmonds-Karp algorithm and how it's different from the f-augmenting path?

Thanks.

Answer 1

You are correct that for each edge we have two endpoints, but that doesn't mean that the number of edges $|E(G)|$ is bounded by $2|V(G)|$. For example, consider a graph where there are $n$ nodes and every possible edge is present (the complete graph $K_n$). Then the number of edges is $\binom{n}{2} = \Theta(n^2)$, since each pair of nodes contributes one edge.

The general idea behind Edmonds-Karp is similar to that of Ford-Fulkerson: find an augmenting path and increase the flow along the path. However, Edmonds-Karp specifically does this by finding, of all possible augmenting paths, the shortest such augmenting path in the graph. This can be done using something like a breadth-first search. (In that sense, you can think of Edmonds-Karp as a very simple optimization on Ford-Fulkerson.)