Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Complexity, optimization | Reply
I implemented "Successive Shortest Path Algorithm" from the tutorial. Works great! Thanks for this article, Zealint.

However I noticed a big performance gain after removing Bellman-Ford call completely. This v*e cost may take significant part of execution time, like 1/3, especially if maxFlow value is less than v. For example in the assignment problem v*e means 4 * n^3. If there are no negative edges (except returning edges that have always negative cost), Dijkstra call should be done instead of Bellman-Ford.