Course contentsShow
← Computer Science
Lesson 988 of 2,87223. Shortest Path AlgorithmsFree lesson

SPFA: Shortest Path Faster Algorithm

Queue-based optimization of Bellman-Ford that often runs faster in practice.

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

  1. Initialize distances (source = 0, others = infinity)
  2. Add source vertex to queue
  3. While queue is not empty:
    • Dequeue a vertex u
    • For each neighbor v of u:
      • Try relaxing edge (u, v)
      • If v's distance improved and v isn't already in queue, enqueue v

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.