One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS.
Could we create the level graph from sink to source instead of source to sink? Of course when subsequently doing the DFS on the level graph we would have to go down the levels rather than up.
I would expect this slight variation to lead to less dead ends during the DFS, resulting in a somewhat faster algorithm. I implemented the change and it supports my expectations. The performance improvement is minor but consistent in my test cases (e.g.: random graphs).
I could not find any literature about this online, and I study CS by myself so I cannot ask a teacher.
- Is the change valid, or does it break the algorithm in a way I did not anticipate?
- I can think of graphs in which the change would have a worse performance (i.e.: simple paths from source to sink, complicated paths from sink to dead ends). Is there a class of problems where these graphs are commonplace?
- Anything else I should know or worry about?