A queue based Bellman Ford
The Shortest Path Faster Algorithm, or SPFA, is a queue driven variant of Bellman Ford. Plain Bellman Ford blindly relaxes every edge each sweep, even edges whose endpoints did not change. SPFA only processes a node when its distance has actually been updated.
How it works
Keep a queue of nodes whose distance recently improved. Pop a node, relax its outgoing edges, and for any neighbor that improves, push it onto the queue if it is not already there.
- Start with the source in the queue.
- Pop a node and relax its edges.
- Enqueue neighbors whose distance dropped.
In practice SPFA is often much faster than Bellman Ford, though its worst case remains the same, so adversarial graphs can slow it dramatically.
Key idea
SPFA improves on Bellman Ford by relaxing only nodes whose distance changed, driven by a work queue, which is usually faster in practice despite an unchanged worst case.