Explain the Bellman-Ford optimization (SPFA).

Explain the Bellman-Ford optimization (SPFA).

Approach: Describe the queue-based version of Bellman-Ford.

The Shortest Path Faster Algorithm (SPFA) is an improvement of the Bellman-Ford algorithm that uses a queue to track nodes whose distances have been updated, reducing redundant relaxations.

Follow-up: What is the worst-case complexity of SPFA?

Key concepts: queue, relaxation, average O(E).