feat: Add Shortest Path Faster Algorithm Implementation #686
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Collaborator
Author
|
Made the rebase to start a new branch based on |
Now the SPF benchmark shows `1,599.55 ns/iter (+/- 22.69)` on my computer. The previous version had about `80,500.00 ns/iter`. For comparison, `bellman_ford` has `51,704.94 ns/iter (+/- 405.06)`. Of course, `spfa` performance is more sensitive than `bellman_ford` to the choice of the initial vertex, but even in the "bad case" performance turns out to be 10 times better than the version with `VecDeque`.
github-merge-queue bot
pushed a commit
that referenced
this pull request
Apr 5, 2025
A sufficient number of proposed changes have accumulated to combine them and publish a new major release numbered `0.8.0`. BREAKING CHANGE: This will require the user to provide extra type parameter in some APIs (Read more in #747). ## List of changes - [x] #747 The main innovation of the current release, the long-awaited feature that has become very relevant due to the transition of dependent projects to support `no_std`. - [x] #662 - [x] #611 - [x] #728 - [x] #686 - [x] #737 - [x] #720 - [x] #718 ## Note There are still a large number of PRs that we want to adopt in the near future, so we should expect at least a release of `0.8.1` soon after the completion of `0.8.0`. Thank you all for participating! --------- Co-authored-by: Agustin Borgna <agustinborgna@gmail.com>
This was referenced Apr 5, 2025
Merged
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
SPFA (Shortest Path Faster Algorithm) is the improved variation of Bellman-Ford.
Time Complexity:
O(|E|), but this bound has not been approved yet.O(|V|*|E|)Space complexity
O(V)Wikipedia says:
A variation of the Bellman–Ford algorithm described by Moore (1959), reduces the number of relaxation steps that need to be performed within each iteration of the algorithm. If a vertex v has a distance value that has not changed since the last time the edges out of v were relaxed, then there is no need to relax the edges out of v a second time. In this way, as the number of vertices with correct distance values grows, the number whose outgoing edges that need to be relaxed in each iteration shrinks, leading to a constant-factor savings in time for dense graphs. This variation can be implemented by keeping a collection of vertices whose outgoing edges need to be relaxed, removing a vertex from this collection when its edges are relaxed, and adding to the collection any vertex whose distance value is changed by a relaxation step. In China, this algorithm was popularized by Fanding Duan, who rediscovered it in 1994, as the "shortest path faster algorithm".[6]
About implementation
I used a stack instead of a queue to improve performance. In this regard, there is a slight discrepancy with the classic description of the "SPFA" algorithm, but this option was also tested on random tests against Bellman-Ford here.