labelcorrecting

Label correcting, also spelled as label-correcting, refers to a class of algorithms for solving the single-source shortest path problem in directed graphs, particularly when edges may have negative weights but no negative cycles. The core idea is to maintain tentative distance labels (the current best estimates of shortest-path distances) for vertices and to iteratively update these labels by relaxing arcs, propagating improvements through the graph until stability is reached.

In a typical label-correcting approach, the source vertex is assigned a distance of zero and all other vertices are given infinity. A worklist (often a queue or deque) contains vertices whose label has recently changed. While the worklist is not empty, a vertex u is removed, and all outgoing edges (u, v) are relaxed: if distance[u] + w(u, v) < distance[v], the distance to v is updated and v is added to the worklist if not already present. The process terminates when no further relaxations occur, and the resulting distances are the shortest path distances from the source.

The method encompasses several implementations. Bellman-Ford can be viewed as a label-correcting algorithm that relaxes all edges in each pass, repeated |V|−1 times. A practical and widely used variant is the Shortest Path Faster Algorithm (SPFA), which processes vertices from a worklist and often runs faster in practice. Variants use different processing orders, such as FIFO or LIFO, and heuristics like Small Label First (SLF) or Large Label Last (LLL) to reduce iterations. Negative cycle detection is typically incorporated by tracking relaxations or counts of updates.

Label correcting is applicable when negative edge weights are present but no negative cycles, and it is related to other shortest-path methods like Dijkstra’s algorithm and Bellman-Ford. It is also used within Johnson’s algorithm for all-pairs shortest paths by reweighting edges to eliminate negative weights.