Skip to content
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

Implement shortest paths algorithm from "Negative-Weight Single-Source Shortest Paths in Near-linear Time" paper #38

Open
pnevyk opened this issue Jan 21, 2023 · 0 comments
Labels
algorithm Algorithm implementation

Comments

@pnevyk
Copy link
Owner

pnevyk commented Jan 21, 2023

source

I haven't studied the paper yet, but I would like to have this included in the library. The reasons are:

  • There would be an implementation of an algorithm for shortest paths with negative weights faster than Bellman-Ford (there have been other algorithms, but this was is claiming the best time complexity bound.
  • The abstract claims that the algorithm is "simple". Whereas it is definitely more complex than Bellman-Ford, it should be simpler than recent alternatives.
  • Implementing the algorithm will show if our API and infrastructure is sufficient for a modern algorithm, or show gaps that we need to fill.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
algorithm Algorithm implementation
Projects
None yet
Development

No branches or pull requests

1 participant