New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Suggestions about D´Esopo-Pape algorithm and SPFA #438
Comments
I agree. I've never understood why D`Esopo-Pape is so much used on the original e-maxx. Especially since nobody else uses that one. I'm not sure if I have time in the next days to replace implementations with SPFA. But you are welcome to make any pull-requests yourself. |
prprprpony
added a commit
to prprprpony/e-maxx-eng
that referenced
this issue
Oct 24, 2019
…nd assignment problem with SPFA (cp-algorithms#438)
Merged
jakobkogler
pushed a commit
that referenced
this issue
Oct 24, 2019
ChamanAgrawal
pushed a commit
to ChamanAgrawal/e-maxx-eng
that referenced
this issue
Oct 19, 2020
replace implementations of shortest path algotirhm in min cost flow and assignment problem with SPFA (cp-algorithms#438)
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Firstly, in the articles of Minimum-cost flow and assignment problem, D´Esopo-Pape algorithm is chose as the algorithm for shortest path.
However, its worst case time complexity is exponential.
Why not use SPFA instead?
Its implementation is basically the same as D´Esopo-Pape algorithm, but has better worst case time complexity (O(nm)).
Secondly, both SPFA and D´Esopo-Pape algorithm are said to be "quite fast in practice" in the ariticles, but none of them contain any figure from experiments to support the statement.
The text was updated successfully, but these errors were encountered: