Dijkstra with Potentials, in depth: feasible potentials, measured landmark choice, averaged bidirectional search and reuse after weight changes

The identity, and the sign convention

Given a potential π, define the reduced weight of edge (u, v) as w_π(u, v) = w(u, v) − π(u) + π(v). Sum it along any path P from s to t. The inner terms telescope, leaving w_π(P) = w(P) − π(s) + π(t). Every s-to-t path shifts by the same constant, so the shortest path under w_π is the shortest path under w. The potential is feasible when every reduced weight is non-negative. Then Dijkstra on w_π is correct, and the true distance is the reduced distance plus π(s) minus π(t).

Sign conventions differ between sources, and mixing them is a classic bug. Here π(v) estimates the remaining distance from v to the target, A* style. Read that way, the priority-queue key g(v) + π(v) is exactly A*'s f = g + h. Feasibility w(u, v) + π(v) ≥ π(u) is A*'s consistency condition. Johnson's algorithm and min-cost flow use distances from a source instead, with w + h(u) − h(v), which is the same identity with π = −h. Write down which convention a codebase uses before touching it.

Implementation

The implementation is ordinary lazy-deletion Dijkstra with the potential added to every key. Track the true g separately, so no subtraction is needed at the end:

import heapq

def dijkstra_pot(adj, s, t, pot):
    """pot(v) must be feasible: w(u,v) + pot(v) >= pot(u) for every edge."""
    g = {s: 0}
    done = set()
    pq = [(pot(s), s)]
    settled = 0
    while pq:
        _, u = heapq.heappop(pq)
        if u in done:
            continue                      # stale queue entry
        done.add(u)
        settled += 1
        if u == t:
            return g[u], settled          # safe to stop: feasible pot, t settled
        for v, w in adj[u]:
            ng = g[u] + w
            if v not in g or ng < g[v]:
                g[v] = ng
                heapq.heappush(pq, (ng + pot(v), v))
    return None, settled

With pot = 0 this is plain Dijkstra. The early return at t is the payoff. A feasible potential makes keys pop in non-decreasing order of reduced distance, so t's g is final the moment t is popped. The tighter π is to the true remaining distance, the fewer nodes pop first.

Building potentials from landmarks

Any lower bound on the remaining distance that is consistent works. Geometric bounds need coordinates and a known minimum cost per unit distance, and they are often weak. Landmarks (the ALT method of Goldberg and Harrelson) need neither. Pick a few nodes L, precompute exact distances d(L, ·) with one Dijkstra each, and use the triangle inequality. On an undirected graph, |d(L, t) − d(L, v)| ≤ d(v, t). Each landmark gives a feasible potential. The maximum of feasible potentials is feasible, so take the max over all landmarks.

D = [sssp(L) for L in landmarks]            # k full Dijkstra runs, k * n integers stored

def alt_potential(t):
    dt = [d[t] for d in D]
    return lambda v: max(abs(dt[i] - d[v]) for i, d in enumerate(D))

# farthest selection: each new landmark is the node farthest from those chosen so far
def pick_farthest(k):
    first = argmax(sssp(random_node()))     # start from a peripheral node
    chosen, dmin = [first], sssp(first)
    while len(chosen) < k:
        nxt = argmax(dmin)
        chosen.append(nxt)
        dmin = [min(a, b) for a, b in zip(dmin, sssp(nxt))]
    return chosen

On a directed graph you need both d(L, ·) and d(·, L). The bound is the max of d(L, t) − d(L, v) and d(v, L) − d(t, L), so storage doubles.

Worked example: what the potential buys, measured

To see how much the potential matters, the code above was run on a 150 by 150 grid graph (22,500 nodes) with undirected edges weighted uniformly from 1 to 20. It answered the same 100 random queries with different potentials. Every answer was checked against plain Dijkstra and matched. The column h(s)/d(s,t) shows how much of the true distance the potential knew at the start.

Three lessons follow. First, the geometric bound was nearly useless. The minimum weight is 1 but the average is 10.5, so it knew only 16.5% of the distance and saved 17% of the work. Second, a small number of well-placed landmarks is a 24-fold reduction. Third, placement matters as much as count: 8 farthest landmarks matched 16 random ones. The relationship between h(s)/d and work is steeply non-linear. Going from 0.914 to 0.966 more than halved the nodes settled, because the search's excess work comes from the gap between bound and truth across the whole frontier.

Bidirectional search needs the averaged potential

Bidirectional Dijkstra (see the bidirectional article) meets in the middle and stops early. Combining it with potentials is a trap. The forward search wants π_t (an estimate of distance to t). The reverse search wants π_s (distance from s). Using both naively means the two searches run on different reduced graphs, and the usual stopping rule becomes wrong. The fix, due to Ikeda and colleagues and used in ALT, is the average potential: forward uses p_f = (π_t − π_s)/2 and reverse uses p_r = −p_f. Both searches now run on one reduced graph, p_f is feasible because it averages two consistent bounds, and the ordinary stopping rule (top of forward queue plus top of reverse queue at least the best meeting cost) is valid again.

The halving introduces fractions. Multiply every weight by 2 instead, so reduced weights stay integers.

pf2 = lambda v: lb(v, t) - lb(s, v)            # 2 * p_f, an integer
rw  = lambda u, v, w: 2 * w - pf2(u) + pf2(v)   # same reduced graph for both directions
# ... standard bidirectional Dijkstra on rw, stop when topF + topR >= mu ...
true_distance = (mu + pf2(s) - pf2(t)) // 2

With a fresh set of 16 farthest landmarks, the averaged bidirectional search settled 373 nodes on average against 475 for unidirectional ALT, with every answer exact. Each side's potential is weaker than the full π_t, which is why the gain is 21% rather than the halving bidirectional search gives without potentials.

Reusing a potential after weights change

Potentials are certificates, so they can outlive the query that produced them. Let π be exact distances from s under the old weights, in the source convention (reduced weight w + d(u) − d(v)). This is what min-cost flow and incremental routing reuse. Increasing an edge weight only raises its reduced weight, so the potential stays feasible. Decreasing one can make it negative. On the grid, applying 1,000 random weight increases left zero violated edges. Dividing just 10 random weights by three left 4 violated edges. The other six had enough slack to absorb the drop.

So a cheap verification pass decides what to do. If there are no violations, keep the old potential; it still guides the search, only less tightly. If there are a few, repair locally by running a label-correcting pass seeded at the violated edges' heads, or fall back to π = 0 for that query. Landmark potentials behave the same way. Weight increases keep every lower bound valid. Decreases can turn a landmark distance into an overestimate, so rerun the affected landmarks or drop them until they are rebuilt.

def violations(adj, pi):
    """Edges with negative reduced weight under a source-convention potential."""
    return [(u, v, w) for u in adj for v, w in adj[u]
            if w + pi[u] - pi[v] < 0]

Failure modes

• Infeasible potential, silent wrong answers. An overestimating heuristic or a stale landmark gives a negative reduced weight. Early termination at t then returns a path that is not shortest, with no error raised. Run the violation check in tests and after every data update.
• Sign convention mixed up. Using w + π(u) − π(v) with an A*-style π turns the search away from the target. It stays correct only when every reduced weight still happens to be non-negative. Usually it is just slow, or wrong if negative.
• Integer overflow. Reduced weights can be as large as w + |π(u) − π(v)|, and the keys g + π grow with the graph diameter. Use 64-bit integers. The doubled-weight trick for averaged potentials halves the headroom again.
• Floating-point drift. With real-valued weights, a mathematically zero reduced weight can compute as −1e-12. Dijkstra then reorders or reopens nodes. Scale to integers where you can. Otherwise clamp reduced weights at zero only after proving the potential feasible in exact arithmetic.
• Landmark memory. k landmarks cost k integers per node, doubled on directed graphs. Sixteen 4-byte distances for 100 million nodes is 6.4 GB. Store them compressed or pick fewer, better-placed landmarks. The measurements above suggest placement buys more than count.
• Unreachable nodes. A landmark that cannot reach part of the graph has infinite distances there. Exclude it from the max for those nodes rather than subtracting infinities.

Trade-offs

Preprocessing is the whole trade. Plain Dijkstra needs nothing and settles everything closer than t. ALT costs k shortest-path runs and k distances per node, and the table shows it buys a 10-to-24-fold reduction on this graph. Heavier speed-up techniques for road networks, such as contraction hierarchies, go further at the cost of more preprocessing and complexity. They are outside this article. Potentials keep one advantage over most of them. Any feasible potential slots into an unmodified Dijkstra, survives weight increases, and can be verified edge by edge, so a bug shows up as a check failure rather than a wrong route. For negative weights there is no real alternative. Compute one feasible potential with Bellman-Ford, then run Dijkstra on reduced weights as often as you like.

What to do next

1. Write down your potential's sign convention in a comment at its definition.
2. Add the edge-by-edge feasibility check to your tests, and to your data pipeline after every weight update.
3. Measure your baseline: mean nodes settled per query with π = 0, on real query logs.
4. Try ALT with 4, 8 and 16 farthest-selected landmarks, and record nodes settled and memory per node.
5. If you use bidirectional search, switch to the averaged potential and confirm exactness against plain Dijkstra on a few thousand random queries.
6. Decide your policy for weight decreases: local repair, landmark rebuild or a fallback to π = 0. Test it with injected decreases.
7. Keep everything in 64-bit integers, scaled if needed.