10.14 Using Distance Labels and Relaxation Correctly

Every shortest-path algorithm in this chapter appears different on the surface.

BFS uses a queue.

Dijkstra uses a priority queue.

Bellman-Ford repeatedly scans edges.

Floyd-Warshall uses dynamic programming.

A* uses heuristics.

Despite these differences, they all rely on the same fundamental idea:

Distance labels are gradually improved through relaxation.

Understanding this idea provides a unified framework for reasoning about shortest-path algorithms. Instead of memorizing many separate procedures, you can view them as different strategies for managing and updating distance estimates.

This recipe examines distance labels, relaxation, and the invariants that make shortest-path algorithms correct.

Problem

Given a graph and a source vertex, maintain distance estimates that gradually converge to the true shortest-path distances.

For example:

A --4--> B
|         ^
|         |
2         |
|         |
v         |
C --1-----

Initially, the shortest path to B is unknown.

Distance labels must improve over time until the optimal solution is discovered.

Solution

Maintain a distance label for every vertex.

dist := make([]int, n)

Initially:

distance[source] = 0
distance[other] = ∞

For every edge:

u -> v

with weight:

apply relaxation:

candidate := dist[u] + w

if candidate < dist[v] {
	dist[v] = candidate
}

This operation attempts to improve the current estimate.

Every shortest-path algorithm repeatedly performs this update.

Understanding Distance Labels

A distance label is not necessarily the actual shortest-path distance.

It is merely the best estimate currently known.

Suppose we begin with:

A = 0
B = ∞
C = ∞

and process:

A -> B = 5

The labels become:

A = 0
B = 5
C = ∞

Later we discover:

A -> C = 2
C -> B = 1

Now:

A = 0
C = 2
B = 3

The label for B improved.

The previous estimate was not wrong.

It was merely incomplete.

Shortest-path algorithms progressively refine information until no further improvements are possible.

The Relaxation Operation

Relaxation is the heart of shortest-path computation.

Given:

distance[u]

and edge:

u -> v

we ask:

Can the path through u improve the current distance to v?

Graphically:

distance[u]
     |
     v
u -----> v
      w

The candidate distance becomes:

distance[u] + w

If that value is smaller than the current label:

distance[v]

we update it.

Nothing more complicated is happening.

Every shortest-path algorithm ultimately reduces to repeated applications of this simple rule.

A Universal View of Shortest-Path Algorithms

The major algorithms differ primarily in relaxation order.

BFS

Relax vertices in distance layers.

Because all edge weights equal one.

Dijkstra

Relax vertices in increasing distance order.

Using a priority queue.

Bellman-Ford

Relax every edge repeatedly.

Until convergence.

DAG Shortest Paths

Relax vertices in topological order.

Taking advantage of acyclicity.

Floyd-Warshall

Relax vertex pairs through intermediate vertices.

Using dynamic programming.

The relaxation rule itself never changes.

Only the scheduling strategy changes.

Visualizing Convergence

Consider:

A -> B = 8
A -> C = 3
C -> B = 2

Initial labels:

A = 0
B = ∞
C = ∞

After relaxing edges from A:

A = 0
B = 8
C = 3

After relaxing:

C -> B

we obtain:

A = 0
B = 5
C = 3

No further improvements exist.

The labels have converged.

These are the true shortest-path distances.

Upper-Bound Interpretation

Distance labels have an important property.

At every moment:

distance[v]

is an upper bound on the true shortest-path distance.

Suppose the optimal distance is:

The algorithm might temporarily store:

The estimate continually decreases.

It never drops below the true answer.

This observation underlies many correctness proofs.

Relaxation only improves labels.

It never invents impossibly good paths.

The Triangle Inequality

Relaxation is closely related to the triangle inequality.

Suppose:

u -> v

has weight:

Then:

distance[v]
≤
distance[u] + w

must hold in a shortest-path solution.

If it does not hold:

distance[v]
>
distance[u] + w

the path through u is better.

A relaxation becomes possible.

Shortest-path algorithms continue relaxing until every edge satisfies this inequality.

At that point, no further improvements remain.

Why Dijkstra Can Finalize Vertices

Dijkstra relies on a stronger invariant.

When the smallest tentative distance is selected:

distance[v]

cannot improve further.

Why?

Because every undiscovered path must pass through vertices whose distances are already at least as large.

Nonnegative edge weights ensure:

future path cost
≥ current distance

Therefore:

distance[v]

is final.

This property explains both the correctness and efficiency of Dijkstra's algorithm.

Why Bellman-Ford Repeats Relaxations

Bellman-Ford does not know which labels are final.

Instead, it repeatedly propagates improvements.

Suppose:

A -> B -> C -> D

Improving:

may later improve:

which later improves:

Multiple passes allow information to travel through the graph.

Eventually every reachable shortest path has been propagated.

Relaxation Trees

Whenever relaxation succeeds:

dist[v] = candidate
parent[v] = u

the predecessor relation changes.

The resulting structure forms a shortest-path tree.

A
├─ B
│  └─ D
└─ C

Every edge in the tree corresponds to a successful relaxation.

The tree records how shortest distances were obtained.

This connection explains why path reconstruction integrates naturally with shortest-path algorithms.

Detecting Completion

Different algorithms detect convergence differently.

BFS

The queue becomes empty.

Dijkstra

The priority queue becomes empty.

Bellman-Ford

A full pass performs no updates.

Floyd-Warshall

All intermediate vertices have been processed.

Each condition indicates the same underlying fact:

No relaxation can further improve any label.

At that moment, shortest-path computation is complete.

Discussion

Distance labels provide a powerful mental model.

Instead of viewing shortest-path algorithms as unrelated techniques, think of them as systems for managing information flow.

Every algorithm begins with incomplete information:

0
∞
∞
∞
∞

Relaxation spreads knowledge through the graph.

Eventually every reachable vertex receives its optimal label.

The specific algorithm determines how efficiently that information propagates.

This perspective makes it easier to understand new shortest-path algorithms because most are merely new relaxation schedules.

Complexity

The cost of relaxation itself is constant.

Operation	Complexity
One relaxation	O(1)
BFS scheduling	O(V + E)
Dijkstra scheduling	O((V + E) log V)
Bellman-Ford scheduling	O(VE)
Floyd-Warshall scheduling	O(V³)

Most performance differences arise from scheduling, not from relaxation.

Common Mistakes

Do not think of distance labels as exact values during execution. They are estimates that improve over time.

Do not forget that successful relaxation must update both distance and predecessor information when path reconstruction is required.

Do not assume every relaxation changes a label. Most attempts fail once distances approach optimal values.

Do not confuse convergence with visiting every vertex. Some algorithms revisit vertices many times before convergence.

Do not overlook the role of edge weights. The correctness of relaxation scheduling often depends on weight assumptions.

Practical Applications

The relaxation framework appears in:

Routing protocols
GPS navigation
Network optimization
Supply-chain planning
Workflow scheduling
Compiler optimization
Constraint systems
Dynamic programming on graphs

Many seemingly unrelated optimization algorithms are variations of relaxation-based information propagation.

Takeaway

Distance labels and relaxation form the conceptual core of shortest-path algorithms. Every major algorithm in this chapter maintains distance estimates and repeatedly improves them through relaxation. The differences between BFS, Dijkstra, Bellman-Ford, DAG shortest paths, and Floyd-Warshall arise primarily from the order in which relaxations occur. Once you understand distance labels as evolving estimates and relaxation as information propagation, shortest-path algorithms become variations of a single underlying idea rather than a collection of unrelated techniques.