-
Notifications
You must be signed in to change notification settings - Fork 312
Closed
Description
Add the queue version of the Bellman-Ford algorithm.
Also known as the “shortest path faster algorithm”.
For the Bellman-Ford algorithm, each iteration requires relaxing all edges. For a vertex v that 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.
Keep a collection of vertices whose outgoing edges need to be relaxed, reducing the number of vertexs to be relaxed.
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm#Improvements
Metadata
Metadata
Assignees
Labels
No labels