How to Learn the Goldberg–Radzik Shortest-Path Algorithm: Admissible Graphs, Topological Scans, Negative Edges and Bellman–Ford Engineering

What if a graph has negative edge weights, but ordinary Bellman–Ford is wasting work by scanning vertices in an unhelpful order? Goldberg–Radzik keeps Bellman–Ford’s robust worst-case guarantee and reorganises the useful relaxations into topological scans of the part of the graph that currently matters.

This Learning Hall article builds from shortest-path relaxation, introduces reduced cost and the admissible graph, explains why DFS ordering can propagate improvements quickly, and then connects the 1993 algorithm to production engineering, negative-cycle detection and recent research on negative-weight single-source shortest paths.

Quick Read

The problem is single-source shortest paths in a directed weighted graph that may contain negative edges.
If a negative cycle is reachable from the source, finite shortest-path distances do not exist for vertices reachable through that cycle.
Bellman–Ford repeatedly relaxes edges and has O(VE) worst-case time.
Goldberg–Radzik also has O(VE) worst-case time but tries to scan vertices in an order that propagates current improvements more effectively.
An edge is currently useful when d[u]+w(u,v)<d[v]. This is equivalent to having negative reduced cost under the current labels.
Useful edges form an admissible subgraph.
DFS is used to organise reachable admissible vertices into an order suitable for a linear relaxation scan.
The method is especially interesting as an example of algorithm engineering: preserve a strong bound while improving practical work ordering.
Modern negative-weight SSSP research still uses Goldberg–Radzik as an important practical baseline.

1. Beginner Level: The Relaxation Operation

Let d[v] be our current best known distance from source s to vertex v. For an edge u→v of weight w(u,v), relaxation asks:

if d[u] + w(u,v) < d[v]:
    d[v] = d[u] + w(u,v)
    parent[v] = u

Every correct label-correcting shortest-path algorithm is, at some level, deciding which relaxations to attempt and in what order.

2. Why Negative Edges Change the Game

Dijkstra’s algorithm relies on the fact that once the smallest tentative distance is settled, nonnegative edges cannot later create a cheaper route back to it. Negative weights remove that monotonicity.

Bellman–Ford handles arbitrary edge signs by repeatedly propagating improvements. It is robust, simple and important—but it may scan many edges before an improvement reaches the part of the graph where it matters.

For related foundations, see Johnson’s Algorithm, which also uses Bellman–Ford reasoning but for graph reweighting and all-pairs shortest paths. This article owns the Goldberg–Radzik scan-order method.

3. Reduced Cost as a Diagnostic

Given current distance labels d, define the reduced cost of edge u→v:

r(u,v) = d[u] + w(u,v) - d[v]

If r(u,v)<0, the edge can improve d[v] right now. Such an edge is often called admissible in descriptions of Goldberg–Radzik. The set of these edges changes as labels improve.

4. The Admissible Graph

Take the original vertices but keep only currently admissible edges. This creates a temporary graph describing where distance improvements can flow under the present labels.

Instead of scanning the whole graph in an arbitrary global order, Goldberg–Radzik focuses on the region reachable from vertices whose labels have become active and tries to order those useful relaxations so one improvement can feed the next during the same scan.

5. Why Topological Order Helps

On a DAG, single-source shortest paths are easy: process vertices in topological order and relax outgoing edges once. Every predecessor that can improve a vertex is handled before that vertex is scanned.

Goldberg–Radzik borrows this idea dynamically. The admissible graph is not guaranteed to remain a DAG in every raw form, but DFS can organise the relevant structure into a scan order, with implementation rules for cycles and back edges. The aim is to make a round behave more like a productive DAG relaxation and less like a blind Bellman–Ford pass.

6. One Round at a High Level

start with vertices whose labels changed

1. discover the reachable admissible region
2. use DFS to create a useful scan order
3. scan vertices in that order
4. relax outgoing edges
5. collect vertices whose labels changed
6. repeat while improvements remain

The details of the admissible DFS and cycle treatment matter for a faithful implementation, but this round structure captures the engineering idea: construct an order from the current geometry of improvements instead of using a fixed edge order.

7. A Small Example

Suppose s→a has weight 8, s→b has weight 2, b→a has weight −5, a→c has weight 3 and b→c has weight 10. An early label d[a]=8 is later improved through b to −3. Once that happens, a→c may become admissible and can immediately improve c to 0.

A poor scan order might visit c before a and postpone this propagation until another round. A topology-informed scan tries to visit a before c once the current admissible structure reveals that dependency.

8. High-Level Pseudocode

GOLDBERG_RADZIK(G, s):
    d[*] = infinity
    parent[*] = NIL
    d[s] = 0
    changed = {s}

    while changed is not empty:
        order = DFS_ADMISSIBLE_REGION(G, d, changed)
        changed = empty set

        for u in order:
            for each edge (u,v,w):
                if d[u] + w < d[v]:
                    d[v] = d[u] + w
                    parent[v] = u
                    changed.add(v)

        if reachable negative cycle is detected:
            report unbounded shortest paths

    return d, parent

This pseudocode deliberately leaves the DFS helper as a named operation. A complete implementation should follow a primary description or a trusted library, especially for back-edge handling and negative-cycle detection.

9. Worst-Case Complexity

Goldberg and Radzik proved an O(VE) worst-case bound, matching classical Bellman–Ford in asymptotic order. The gain is therefore not a better worst-case exponent. It is a better organisation of practical work on many instances.

This distinction matters. Algorithm engineering often improves the constant factors, scan counts, cache behaviour or propagation order while intentionally preserving a known theoretical guarantee.

10. Negative Cycles

If a negative-weight cycle is reachable from s, walking around it repeatedly makes path cost arbitrarily small. There is no finite shortest-path solution downstream of that cycle.

A production implementation must therefore define its contract clearly: return distances only when finite shortest paths exist, and otherwise signal or identify a reachable negative cycle. Do not silently return partially improved labels as if they were final answers.

11. Goldberg–Radzik vs Bellman–Ford

Bellman–Ford: very simple, predictable, easy to verify.
Goldberg–Radzik: more machinery, but attempts to propagate improvements in a more useful order.
Both: support negative edges and have O(VE) classical worst-case bounds.
Choice: depends on graph family, implementation maturity, negative-cycle needs and measured workload.

12. Modern Context

Negative-weight shortest paths have seen major theoretical advances beyond the classical O(VE) landscape. Recent algorithm-engineering work has investigated newer near-linear methods and compared them experimentally against Goldberg–Radzik. That is a useful professional signal: an algorithm can be decades old and still remain an important baseline because it combines solid theory with strong practical behaviour.

13. Implementation Failure Modes

Using Dijkstra on negative edges. The settled-distance invariant is invalid.
Calling every edge admissible. Admissibility is relative to the current labels.
Using stale reduced costs. Re-evaluate against current d values.
Confusing zero reduced cost with strictly improving relaxation. Specify the exact rule used by the chosen implementation.
Ignoring unreachable vertices. Infinity arithmetic needs explicit handling.
Returning results in the presence of a reachable negative cycle. Treat this as a contract failure, not a strange distance.
Assuming fewer scans means faster runtime. DFS ordering itself has cost; benchmark real instances.

14. Testing Strategy

Nonnegative graph: compare with Dijkstra.
Negative edges but no negative cycle: compare with Bellman–Ford.
Reachable negative cycle: require explicit detection.
Unreachable negative cycle: verify source-reachable distances remain meaningful according to the API contract.
Disconnected vertices and infinite labels.
Parallel edges with different weights.
Random small graphs checked by Bellman–Ford oracle.
Instrument rounds, edge relaxations and DFS visits separately.

15. How to Learn It Efficiently

Begin with a table containing d[u], d[v], edge weight and reduced cost. Learners should first decide which edges are admissible without writing code. Next, give a completed DFS ordering and ask them to perform the linear scan. Then fade the ordering and require them to produce it. Only after both subgoals are stable should they combine them into a full round.

This subgoal structure—identify useful edges, order useful work, propagate labels, verify termination—fits well with worked examples and PRIMM. Predict which label changes, run the implementation, investigate the admissible graph, modify one weight, then make a new test case designed to change the scan order.

16. Professional Engineering Questions

Do weights fit safely in the chosen numeric type?
Can addition overflow before comparison?
Are weights integers, floating point, decimals or arbitrary precision?
How is infinity represented?
Does the library expose the negative cycle or only report its existence?
Are predecessor trees required or only distances?
Does the workload contain many repeated queries on the same graph?
Would reweighting, preprocessing or a different graph representation dominate algorithm choice?

17. Practice Problems

Compute reduced costs for every edge after one Bellman–Ford-style relaxation round.
Draw the resulting admissible graph.
Find a topological order when the admissible region is acyclic.
Change one edge weight so the useful scan order changes.
Construct a reachable negative cycle and explain why finite distances cease to exist.
Compare the number of edge scans performed by Bellman–Ford and Goldberg–Radzik on the same generated graph family.
Use NetworkX or another trusted implementation as a differential-testing oracle.

18. Sources and Further Reading

Final idea: Goldberg–Radzik teaches a professional habit that reaches far beyond shortest paths: when the primitive operation is already correct, performance may depend on scheduling useful work in the right order. Relaxation is unchanged. What changes is the temporary graph we build from current mistakes and the order in which we repair them.

Small Group Tutorials