SPFA

Short Path Faster Algorithm (SPFA) is an algorithm for computing single-source shortest paths in graphs that may contain negative edge weights but no negative cycles reachable from the source. It is a relaxation-based improvement of the Bellman-Ford approach and often performs well in practice.

SPFA maintains a queue of vertices whose distance was recently updated. Distances are initialized with +infinity, except dist[source] = 0. The source is enqueued. While the queue is not empty, a vertex u is dequeued, marked as not in the queue, and all outgoing edges (u, v) with weight w are relaxed: if dist[u] + w < dist[v], update dist[v], optionally record a predecessor, and enqueue v if it is not already in the queue.

To detect negative-weight cycles, SPFA counts how many times each vertex has been relaxed or enqueued; if this count exceeds the number of vertices, a negative cycle reachable from the source exists. In graphs without such cycles, the algorithm terminates with correct shortest-path distances.

Complexity varies with the input; the worst-case time is O(VE), matching Bellman-Ford, but many inputs run much faster. Space complexity is O(V + E) for distances, queue, and edge data. Practical implementations often include optimizations such as Small Label First (SLF) or Large Label Last (LLL) to prioritize promising relaxations and reduce queue churn. SPFA can be used on directed graphs and, with appropriate edge representation, on undirected graphs.

SPFA remains popular in competitive programming and certain routing problems due to its simplicity and strong average performance on sparse graphs; however, its worst-case behavior can be adversarial, and in some cases alternative algorithms (such as Dijkstra for non-negative weights) may be preferable.