Skip to content

Potential Functions

Dijkstra breaks on negative edges. Bellman-Ford handles them but costs \(O(VE)\). What if you could transform negative edges into non-negative ones, run Dijkstra, then undo the transformation? That's exactly what a potential function does. It's the algebraic trick behind Johnson's algorithm — and it solves a class of "maximize gain" problems that look nothing like shortest paths.

The Problem with Negative Edges

A* search: heuristic function guides exploration toward target

Potential reweighting: transform edge weights so all become non-negative

Dijkstra's greedy invariant: when you pop a node, its distance is final. This relies on all edge weights being non-negative. If an edge has weight \(-5\), a longer path through an unprocessed node might actually be shorter. The greedy choice fails.

Bellman-Ford fixes this by relaxing all edges \(V-1\) times. But that's \(O(VE)\) — too slow for large graphs.

💡 Key insight. A potential function shifts all edge weights up so they're non-negative, without changing which path is shortest. It's not a hack — it's a mathematically rigorous reweighting that preserves shortest-path structure.

The Reweighting Formula

Choose a potential function \(h(v)\) for each node \(v\). Define the new weight:

\[w'(u, v) = w(u, v) + h(u) - h(v)\]

Two critical properties:

  1. Path costs shift predictably. For any path \(s \to v_1 \to v_2 \to \cdots \to t\), the reweighted cost equals the original cost plus \(h(s) - h(t)\). The intermediate potentials telescope and cancel.

  2. Shortest paths don't change. Since \(h(s) - h(t)\) is the same for ALL paths from \(s\) to \(t\), the path with minimum original cost also has minimum reweighted cost.

After running Dijkstra on the reweighted graph:

\[\text{real\_dist}[v] = \text{dijkstra\_dist}[v] - h(s) + h(v)\]

⚠ Gotcha. The potential function must make ALL edges non-negative. If \(w'(u,v) < 0\) for any edge, Dijkstra still fails. Choosing the right \(h\) is the art.

AtCoder abc237_e — Skiing

Problem. \(N\) plazas connected by \(M\) slopes. Plaza \(i\) has height \(h_i\). Each slope connects plazas \(u\) and \(v\) (bidirectional). Moving from \(u\) to \(v\):

  • Downhill (\(h_u \geq h_v\)): gain fun equal to \(h_u - h_v\).
  • Uphill (\(h_u < h_v\)): lose fun equal to \(2 \times (h_v - h_u)\).

Start at plaza 1. Maximize total fun. Fun can be negative.

Reformulating as Shortest Path

Maximizing fun = minimizing negative fun = minimizing cost where:

  • Downhill edge \(u \to v\): cost \(= -(h_u - h_v)\) (negative — we gain).
  • Uphill edge \(u \to v\): cost \(= 2(h_v - h_u)\) (positive — we lose).

This graph has negative edges. Dijkstra fails directly.

Applying the Potential Function

Set \(h(v) = \text{height of plaza } v\) as the potential. Reweight each edge:

Downhill (\(h_u \geq h_v\)):

\[w'(u,v) = -(h_u - h_v) + h_u - h_v = 0\]

Uphill (\(h_u < h_v\)):

\[w'(u,v) = 2(h_v - h_u) + h_u - h_v = h_v - h_u\]

Both are \(\geq 0\). Dijkstra works on the reweighted graph.

💡 Key insight. The heights themselves are the perfect potential function. Downhill edges become free (cost 0). Uphill edges keep a reduced but non-negative cost. The physics of the problem hands you the potential on a platter.

Full Trace

5 plazas, heights: \(h = [10, 5, 3, 0, 8]\). Edges: \(1{-}2\), \(2{-}3\), \(3{-}4\), \(2{-}5\).

Original edge costs (both directions):

Edge Type Original Cost Reweighted \(w'\)
1 \(\to\) 2 downhill \(-(10-5)=-5\) \(-5+10-5=0\)
2 \(\to\) 1 uphill \(2(10-5)=10\) \(10+5-10=5\)
2 \(\to\) 3 downhill \(-(5-3)=-2\) \(-2+5-3=0\)
3 \(\to\) 2 uphill \(2(5-3)=4\) \(4+3-5=2\)
3 \(\to\) 4 downhill \(-(3-0)=-3\) \(-3+3-0=0\)
4 \(\to\) 3 uphill \(2(3-0)=6\) \(6+0-3=3\)
2 \(\to\) 5 uphill \(2(8-5)=6\) \(6+5-8=3\)
5 \(\to\) 2 downhill \(-(8-5)=-3\) \(-3+8-5=0\)

Dijkstra from plaza 1 on reweighted graph:

Step Pop \((d', u)\) dist'[] after relaxation
Init — \([0, \infty, \infty, \infty, \infty]\)
1 \((0, 1)\) \([0, 0, \infty, \infty, \infty]\)
2 \((0, 2)\) \([0, 0, 0, \infty, 3]\)
3 \((0, 3)\) \([0, 0, 0, 0, 3]\)
4 \((0, 4)\) \([0, 0, 0, 0, 3]\)
5 \((3, 5)\) \([0, 0, 0, 0, 3]\)

Convert back: \(\text{real\_dist}[v] = \text{dist}'[v] - h[1] + h[v]\)

Plaza \(v\) \(h[v]\) \(\text{dist}'[v]\) \(\text{real\_dist}[v]\) Fun \(= -\text{real}\)
1 10 0 \(0 - 10 + 10 = 0\) 0
2 5 0 \(0 - 10 + 5 = -5\) 5
3 3 0 \(0 - 10 + 3 = -7\) 7
4 0 0 \(0 - 10 + 0 = -10\) 10
5 8 3 \(3 - 10 + 8 = 1\) \(-1\)

Answer: 10. Ski all the way downhill from plaza 1 (height 10) to plaza 4 (height 0), gaining 10 fun. Going to plaza 5 requires climbing uphill from 2, which kills your fun.

Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> h(N + 1);
    for (int i = 1; i <= N; i++) cin >> h[i];

    vector<vector<pair<int,long long>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        // Reweighted costs
        long long w_uv, w_vu;
        if (h[u] >= h[v]) {
            w_uv = 0;               // downhill: free
            w_vu = h[u] - h[v];     // uphill: reduced cost
        } else {
            w_uv = h[v] - h[u];
            w_vu = 0;
        }
        adj[u].push_back({v, w_uv});
        adj[v].push_back({u, w_vu});
    }

    // Dijkstra from node 1
    vector<long long> dist(N + 1, LLONG_MAX);
    dist[1] = 0;
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // Answer: max over all v of (h[1] - h[v] - dist'[v])
    long long ans = 0;
    for (int v = 1; v <= N; v++) {
        if (dist[v] < LLONG_MAX) {
            ans = max(ans, h[1] - h[v] - dist[v]);
        }
    }
    cout << ans << endl;
}

Johnson's Algorithm: The General Case

The Skiing problem handed us the perfect potential (heights). What if there's no natural potential?

Johnson's algorithm for all-pairs shortest paths:

  1. Add a virtual node \(s\) with zero-weight edges to all real nodes.
  2. Run Bellman-Ford from \(s\). Set \(h(v) = \text{dist}(s, v)\).
  3. Reweight: \(w'(u,v) = w(u,v) + h(u) - h(v)\).
  4. Run Dijkstra from each node on the reweighted graph.
  5. Adjust: \(\text{real\_dist}[u][v] = \text{dijkstra\_dist}[u][v] - h(u) + h(v)\).

Why does this work? The triangle inequality of shortest paths guarantees \(h(v) \leq h(u) + w(u,v)\). Rearranging: \(w'(u,v) = w(u,v) + h(u) - h(v) \geq 0\). Every reweighted edge is non-negative.

Time: \(O(VE)\) for Bellman-Ford + \(O(V(V+E) \log V)\) for \(V\) Dijkstra runs. Beats Floyd-Warshall's \(O(V^3)\) on sparse graphs.

💡 Key insight. Bellman-Ford's shortest-path distances satisfy the triangle inequality by definition. That's exactly what makes them a valid potential function. The math is circular in the most elegant way.

LC 1631 — Path With Minimum Effort

Problem. A 2D grid of heights. Moving from cell \((r_1, c_1)\) to adjacent \((r_2, c_2)\) costs \(|h[r_1][c_1] - h[r_2][c_2]|\). Find the path from top-left to bottom-right that minimizes the maximum edge cost along the path.

This isn't a sum-of-weights problem — it's a minimax path. But the height-based cost structure connects to our theme.

Solution. Dijkstra with a twist: instead of summing costs, take the max. The priority queue stores (max_effort_so_far, cell). Relaxation uses max instead of addition.

int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
vector<vector<int>> effort(R, vector<int>(C, INT_MAX));
effort[0][0] = 0;
priority_queue<tuple<int,int,int>,
               vector<tuple<int,int,int>>,
               greater<>> pq;
pq.push({0, 0, 0});

while (!pq.empty()) {
    auto [e, r, c] = pq.top(); pq.pop();
    if (e > effort[r][c]) continue;
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
        int ne = max(e, abs(heights[r][c] - heights[nr][nc]));
        if (ne < effort[nr][nc]) {
            effort[nr][nc] = ne;
            pq.push({ne, nr, nc});
        }
    }
}
return effort[R-1][C-1];

No potential function needed — absolute values are already non-negative. But notice the pattern: edge costs derived from node heights. In Skiing, the heights created negative edges that needed reweighting. Here, the absolute value keeps everything non-negative naturally.

When to Reach for Potential Functions

Signal Action
Negative edges from "gains" or "downhill" Use natural heights/values as potential
All-pairs shortest paths with negative edges Johnson's algorithm
"Maximize gain" along a path Negate to minimize, reweight to remove negatives
Edge weights depend on node properties Node property is often the potential

⚠ Gotcha. Potential functions cannot fix negative cycles. If a negative cycle exists, no reweighting can make all edges non-negative. The cycle's total reweighted cost equals its original cost (the potentials telescope and cancel around the cycle). Bellman-Ford detects negative cycles; Dijkstra with potentials does not.

Exercises

  1. Verify the telescoping. For a path \(1 \to 3 \to 5 \to 2\) with potential \(h\), expand \(w'(1,3) + w'(3,5) + w'(5,2)\) and confirm it equals \(w(1,3) + w(3,5) + w(5,2) + h(1) - h(2)\).

  2. Bad potential. If you set \(h(v) = 0\) for all \(v\), what happens to the reweighted edges? Is this useful?

  3. Negative cycle. Construct a 3-node graph with a negative cycle. Show that reweighting with Bellman-Ford potentials preserves the negative cycle. What does Bellman-Ford report?

Problems

Problem Link Difficulty
AtCoder abc237_e — Skiing atcoder.jp/contests/abc237/tasks/abc237_e Hard
LC 1631 — Path With Minimum Effort leetcode.com/problems/path-with-minimum-effort Medium