10.15 Using Potentials to Reweight Graphs

Negative edge weights complicate shortest-path algorithms.

Dijkstra's algorithm is efficient because it assumes that once a vertex receives the smallest tentative distance, that distance can never improve. Negative edges break this assumption. A path that appears expensive today may become cheaper tomorrow after traversing a negative edge.

Bellman-Ford handles negative edges correctly, but its running time is significantly higher than Dijkstra's.

This raises an interesting question:

Can we transform a graph with negative edges into an equivalent graph with only nonnegative edges?

Surprisingly, the answer is yes.

The key idea is to assign a numerical potential to every vertex and use those potentials to reweight edges. The resulting graph preserves shortest paths while eliminating negative weights.

This technique forms the foundation of Johnson's algorithm and appears throughout graph optimization.

Problem

Given a graph containing negative edge weights but no negative cycles, transform the graph so that all edge weights become nonnegative while preserving shortest-path relationships.

Consider:

A --2--> B
|
|
4
|
v
C --(-3)--> B

The shortest path from A to B is:

A -> C -> B

with total cost:

4 + (-3) = 1

The graph contains a negative edge.

We would like to eliminate that negative edge without changing shortest-path answers.

Solution

Assign each vertex a potential:

h(v)

Then redefine every edge weight:

w'(u, v)
=
w(u, v)
+
h(u)
-
h(v)

The new weight:

w'

is called the reweighted edge cost.

If the potentials are chosen correctly, every edge becomes nonnegative.

A Small Example

Suppose:

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

Choose potentials:

h(A) = 0
h(B) = -1
h(C) = 2

Reweight:

A → B

2 + 0 - (-1)
=
3

A → C

4 + 0 - 2
=
2

C → B

-3 + 2 - (-1)
=
0

The transformed graph becomes:

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

All edge weights are now nonnegative.

Why Shortest Paths Are Preserved

At first glance, modifying edge weights appears dangerous.

Suppose a path is:

v₀ -> v₁ -> v₂ -> ... -> vk

The reweighted cost becomes:

w(v₀,v₁)
+ h(v₀)
- h(v₁)

+

w(v₁,v₂)
+ h(v₁)
- h(v₂)

+

...

+

w(vk-1,vk)
+ h(vk-1)
- h(vk)

Notice what happens.

Every intermediate potential cancels:

+h(v₁) - h(v₁)
+h(v₂) - h(v₂)
...

The result simplifies to:

original path cost
+
h(source)
-
h(destination)

The adjustment depends only on the endpoints.

Every path between the same two vertices receives exactly the same offset.

Therefore:

Shortest path ordering remains unchanged.

The cheapest path before reweighting remains the cheapest path afterward.

Finding Useful Potentials

The challenge is selecting:

h(v)

correctly.

Johnson's algorithm obtains potentials from Bellman-Ford.

Add a new vertex:

S

connected to every vertex with zero-cost edges.

S -> A = 0
S -> B = 0
S -> C = 0
...

Run Bellman-Ford from:

S

The resulting distances become the potentials.

h(v) = distance(S, v)

These values satisfy:

h(v)
≤
h(u) + w(u,v)

for every edge.

This property guarantees:

w'(u,v)
=
w(u,v)
+
h(u)
-
h(v)
≥ 0

Every reweighted edge is nonnegative.

Verifying Nonnegativity

Suppose Bellman-Ford computes:

h(B) = 5
h(C) = 3

and:

C -> B = 2

Then:

h(B)
≤
h(C) + 2

which implies:

5 ≤ 3 + 2

or:

5 ≤ 5

Now compute:

w'(C,B)
=
2 + 3 - 5
=
0

The reweighted edge is nonnegative.

The argument works for every edge in the graph.

Recovering Original Distances

Dijkstra computes shortest paths in the reweighted graph.

Suppose it returns:

d'(u,v)

To recover the original shortest-path distance:

d(u,v)
=
d'(u,v)
-
h(u)
+
h(v)

This simply reverses the earlier transformation.

The final answer matches the original graph exactly.

Implementing Edge Reweighting

A simple edge transformation looks like:

type Edge struct {
	From   int
	To     int
	Weight int
}

func reweight(
	edges []Edge,
	h []int,
) []Edge {

	result := make([]Edge, len(edges))

	for i, edge := range edges {
		result[i] = Edge{
			From: edge.From,
			To:   edge.To,
			Weight: edge.Weight +
				h[edge.From] -
				h[edge.To],
		}
	}

	return result
}

After reweighting, ordinary Dijkstra can be applied safely.

Connection to Relaxation

Potentials can also be understood through relaxation.

Bellman-Ford produces:

h(v)
≤
h(u) + w(u,v)

for every edge.

Rearranging:

w(u,v)
+
h(u)
-
h(v)
≥ 0

which is precisely the reweighted edge cost.

In other words:

Potentials are distance labels that satisfy all relaxation constraints.

This perspective connects graph reweighting directly to the shortest-path framework developed earlier in the chapter.

Visual Interpretation

Imagine each vertex has a height.

Height(A) = 10
Height(B) = 5
Height(C) = 8

Reweighting adjusts edge costs according to altitude differences.

Moving downhill increases edge cost.

Moving uphill decreases edge cost.

The graph's geometry changes, but every complete path between two fixed vertices receives the same total adjustment.

The optimal route remains unchanged.

This visualization is often useful when reasoning about potentials.

Discussion

Potentials are one of the most elegant ideas in graph theory.

They accomplish three goals simultaneously:

• Remove negative edge weights
• Preserve shortest paths
• Enable efficient algorithms

Many advanced graph algorithms rely on this concept.

Johnson's algorithm is the most famous example, but potentials also appear in:

• Minimum-cost flow
• Network optimization
• Linear programming
• Reduced-cost calculations
• Transportation problems

The idea of transforming a problem into an easier equivalent form is a recurring theme in algorithm design.

Potentials provide a particularly elegant example.

Complexity

Suppose:

• V = vertices
• E = edges

Computing potentials requires Bellman-Ford:

O(VE)

Reweighting edges requires:

O(E)

Running Dijkstra afterward requires:

O((V + E) log V)

The reweighting itself is inexpensive.

The main cost comes from computing the potentials.

Common Mistakes

Do not apply reweighting if the graph contains a negative cycle. Bellman-Ford will fail to produce valid potentials.

Do not forget to convert distances back after running Dijkstra.

Do not assume potentials preserve edge weights. They preserve shortest-path ordering.

Do not compute potentials independently. They must satisfy Bellman-Ford's shortest-path constraints.

Do not confuse potentials with heuristic estimates. Potentials are exact mathematical transformations.

Practical Applications

Potentials appear in:

• Johnson's algorithm
• Minimum-cost flow
• Transportation optimization
• Logistics planning
• Network routing
• Resource allocation
• Graph analytics
• Operations research

Many industrial optimization systems rely on reduced-cost transformations derived from potentials.

Takeaway

Potentials transform graphs with negative edge weights into equivalent graphs with nonnegative weights. By reweighting each edge according to vertex potentials, shortest paths are preserved while enabling efficient algorithms such as Dijkstra. The technique reveals a deep connection between shortest-path distances, relaxation constraints, and graph transformations, making it one of the most powerful ideas in graph optimization.