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!

Get hands-on with 1200+ tech skills courses.