You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Instead of performing both bfs (initialize dist) and dfs (find augmenting path) from source, we can bfs from sink but still dfs from source. Doing so avoids exploring useless nodes that do not take us closer to sink while finding augmenting paths and a crude benchmark shows 10-20% runtime reduction on random graphs. This also makes dist more consistent with the labeling function in Push-relabel algorithm.
The text was updated successfully, but these errors were encountered:
Instead of performing both bfs (initialize dist) and dfs (find augmenting path) from source, we can bfs from sink but still dfs from source. Doing so avoids exploring useless nodes that do not take us closer to sink while finding augmenting paths and a crude benchmark shows 10-20% runtime reduction on random graphs. This also makes dist more consistent with the labeling function in Push-relabel algorithm.
The text was updated successfully, but these errors were encountered: