'Can there be dead ends in Ford fulkerson based algorithm?
Can we remove those edges which don't lead to sink t during DFS in ford fulkerson merhod similar to what we do in dinics algorithm? If not, can you please give an example.
Solution 1:[1]
Got it. Because in ford fulkerson, we can use an augmenting path through reverse edge to reduce a forward edge flow, which might make the forward edge usable in next iteration of DFS. So, removing an edge is not a good idea. Whereas in dinic, dead v can't become usable again once it's dead since there is no chance flow of an edge going away from v be reduced due to lack of reverse edges.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Vivek Kumar |