Ford-Fulkerson Algorithm: The Fine Print

Implementation details

To implement the Ford-Fulkerson algorithm, the first challenge to address is to find a semi-path from a source to a sink in a given flow network. It’s not obvious how to do this efficiently. It is easy to find outgoing edges from a vertex by traversing a single adjacency list, but finding all incoming edges on that vertex requires traversing adjacency lists of all the vertices!