0
$\begingroup$

Depending on where I look, some places (https://courses.engr.illinois.edu/cs473/sp2009/notes/19-maxflowalgs.pdf) describe EK algorithm as choosing the st path with largest bottleneck value, while others (wikipedia) describe it as the shortest path from $s$ to $t$. I'm not sure if they are the same, and I haven't been able to find a proof demonstrating that they are if it is the case. Why does largest bottleneck value correspond to shortest path?

$\endgroup$
1
$\begingroup$

The shortest path and the path with the largest bottleneck are not the same in general.

It is easy to construct a counterexample: pick $G=(V,E)$ with $V=\{a,b,c\}$, and $E=\{ (a,b), (a,c), (c,b) \}$ where $(a,b)$ has capacity $1$ while $(a,c)$ and $(c,b)$ have capacity $2$. The shortest path between $a$ and $b$ consists of the single edge $(a,b)$. The path between $a$ and $b$ with the largest bottleneck is $\langle a,c,b \rangle$.

Besides, the notes that you linked describe and analyze both variants of the Edmonds-Karp algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.