SPFA: Shortest Path Faster Algorithm
What you'll learn: You'll discover a queue-based optimization of Bellman-Ford that often runs much faster in practice by avoiding unnecessary edge relaxations.
The Core Idea
Remember how Bellman-Ford relaxes all edges in every iteration, even when most of those relaxations don't improve any distances? SPFA (Shortest Path Faster Algorithm) fixes this inefficiency.
The key insight: Only vertices whose distances just changed can possibly improve their neighbors' distances.
SPFA maintains a queue of vertices whose distances were recently updated. It only relaxes edges from vertices in this queue. When a relaxation succeeds (a neighbor's distance improves), that neighbor joins the queue. When the queue empties, all shortest paths are found.
How It Differs from Bellman-Ford
Bellman-Ford: "Let me check all E edges, V-1 times, just in case..."
SPFA: "Let me only check edges from vertices that just got better distances!"
Think of it like spreading news: you don't announce yesterday's news to everyone repeatedly. You only tell people when you have new information, and they pass it along only if their information updates.
The Algorithm Flow
- Initialize distances (source = 0, others = infinity)
- Add source vertex to queue
- While queue is not empty:
- Dequeue a vertex
u - For each neighbor
vofu:- Try relaxing edge
(u, v) - If
v's distance improved andvisn't already in queue, enqueuev
- Try relaxing edge
- Dequeue a vertex
Why It's Faster in Practice
On sparse graphs with few "useful" updates, SPFA avoids the wasteful work of Bellman-Ford. Instead of O(VE) worst-case operations, it often runs in O(E) or O(VE) average time, depending on the graph structure.
Key Takeaway: SPFA optimizes Bellman-Ford by using a queue to process only vertices with recently updated distances, dramatically improving performance on typical graphs while still handling negative edges.