1 Problem setting and motivation

1.1 Shortest paths with negative edge weights

In shortest-path problems on directed graphs, each edge has a cost and one seeks minimum-cost paths from a specified source to all other vertices. Classical Dijkstra’s algorithm requires all edge costs to be nonnegative; if negative edges exist, the greedy selection of the next vertex to finalize no longer guarantees correctness.

Many optimization workflows naturally produce negative reduced costs (for example, after dual-variable updates). In such settings, the need arises for a method that still computes shortest paths efficiently despite negative original edge costs.

1.2 Reweighting idea and invariants

The central idea is to maintain a potential value for every vertex and use it to reweight edges. For an edge from \(u\) to \(v\) with original cost \(c(u,v)\), the reduced (reweighted) cost is defined as \[ c'(u,v)=c(u,v)+\pi(u)-\pi(v), \] where \(\pi(\cdot)\) is the vertex potential. The method aims to keep reduced costs nonnegative (or at least nonnegative for relevant edges) so that Dijkstra can run.

A key invariant is that reweighting does not change which paths are optimal when interpreted under the original costs. Potentials are updated using information from computed shortest paths, gradually enforcing nonnegativity conditions needed for Dijkstra’s efficiency.

1.3 Relationship to min-cost flow subroutines

In min-cost flow algorithms, one repeatedly finds shortest augmenting paths in an auxiliary residual network. During iterations, edge costs in the residual graph can become negative, especially for edges with negative reduced costs derived from dual potentials. Dijkstra with potentials is a common subroutine for finding successive shortest paths while keeping each iteration fast.

The overall optimization benefits because potentials from previous iterations can often be reused and updated, avoiding a full re-derivation of shortest paths from scratch using slower algorithms.

2 Fundamentals: potentials and reweighting

2.1 Definition of vertex potentials

A vertex potential is a real-valued function \(\pi:V\to \mathbb{R}\). It is maintained and updated during the algorithm. Intuitively, it acts like a “correction term” that shifts costs along paths so that the greedy structure of Dijkstra remains valid.

Potentials are not unique: adding the same constant to all \(\pi(v)\) leaves reduced costs unchanged. This freedom is commonly exploited in implementations but does not affect correctness.

2.2 Reduced (reweighted) edge costs

Given potentials \(\pi\), each edge’s reduced cost is computed as \[ c'(u,v)=c(u,v)+\pi(u)-\pi(v). \] For a path \(P = (v_0, v_1, \dots, v_k)\), the sum of reduced costs telescopes: \[ \sum_{i=0}^{k-1} c'(v_i,v_{i+1}) = \sum_{i=0}^{k-1} c(v_i,v_{i+1}) + \pi(v_0) - \pi(v_k). \] This telescoping behavior is what allows the algorithm to preserve shortest paths under a suitable interpretation of distances.

2.3 How potentials preserve shortest paths

Let \(d\) be the true shortest-path distance from the source \(s\) under original costs, and let \(d'\) be the shortest-path distance from \(s\) under reduced costs. For any vertex \(v\), \[ d'(v) = d(v) + \pi(s) - \pi(v). \] Rearranging yields \[ d(v)=d'(v)+\pi(v)-\pi(s). \] Therefore, if one computes shortest reduced distances \(d'\) with Dijkstra (under conditions that make it valid), the original shortest distances can be recovered by applying the potential correction.

Moreover, because the relation above holds for every candidate path, the ordering of path costs from \(s\) to \(v\) is preserved: a path is optimal in original costs exactly when it is optimal in reduced costs.

2.4 Conditions for nonnegative reduced costs

Dijkstra’s algorithm requires nonnegative edge costs in the form it operates on. With reduced costs, the requirement becomes: \[ c'(u,v) \ge 0 \quad \text{for edges that may be relaxed during Dijkstra.} \] In practice, the algorithm maintains potentials so that reduced costs are nonnegative on the edges of interest. One common strategy is to initialize potentials using shortest distances from a single run of Bellman–Ford (or another method that tolerates negative edges), ensuring nonnegativity after reweighting.

During successive runs, potentials are updated so that the reduced cost property continues to hold for edges reachable from the current frontier, enabling repeated Dijkstra calls.

3 Algorithm: Dijkstra with potentials (single-source)

3.1 Initialization of potentials

To begin, one needs an initial potential function \(\pi\). Common choices include:

  • \(\pi(v)=0\) for all vertices when original costs are already nonnegative.
  • A potential derived from shortest-path distances computed with a negative-edge-capable algorithm (e.g., Bellman–Ford). If \(\pi(v)\) is set to the shortest distance from \(s\) to \(v\), then the reduced costs become nonnegative when there are no reachable negative cycles.
  • In some contexts (especially min-cost flow), potentials from a previous phase already exist and can be reused as the initial \(\pi\).

The initialization must be such that the resulting reduced costs do not violate Dijkstra’s nonnegativity requirement for edges considered.

3.2 Running Dijkstra on reduced costs

With potentials fixed, the algorithm constructs a reduced-cost view of the graph and runs Dijkstra from \(s\). The priority queue orders vertices by their tentative reduced distance \(d'(v)\).

Relaxation uses reduced costs: \[ \text{if } d'(v) > d'(u)+c'(u,v), \text{ then update } d'(v). \] Because reduced costs are intended to be nonnegative, Dijkstra’s standard invariant holds: once a vertex is extracted as the minimum-key element, its \(d'\) value is finalized.

3.3 Updating potentials from computed distances

After Dijkstra yields reduced distances \(d'\), potentials are updated to enforce continued nonnegativity. A typical update rule is: \[ \pi(v) \leftarrow \pi(v) - d'(v) \quad \text{for all vertices reachable in the Dijkstra run}, \] or equivalently \[ \pi(v) \leftarrow \pi(v) + \Delta(v), \] where \(\Delta(v)\) is derived from the computed shortest distances.

The exact sign convention depends on the implementation’s definition of reduced costs and distance recovery, but the effect is consistent: vertices “move” according to their computed shortest-path distances so that reweighted costs align with the new shortest-path structure.

3.4 Recovering original distances from reduced results

If one wants the original distances from \(s\) under original costs during this run, they can be recovered using the telescoping relation. Using the convention above: \[ d(v) = d'(v) + \pi(v) - \pi(s), \] where \(\pi(v)\) refers to the potentials used during the Dijkstra computation.

If potentials are updated immediately after Dijkstra, implementations typically store either the old potentials or compute distances before overwriting \(\pi\), to avoid confusion between “potentials used to define reduced costs” and “updated potentials.”

3.5 Complexity and data structures

Assuming a graph with \(n\) vertices and \(m\) edges, Dijkstra with a binary heap runs in \(O(m\log n)\) time per call. The extra work for maintaining potentials is linear in the number of vertices whose distances are used.

Data structures commonly include:

  • adjacency lists for edges,
  • arrays for potentials and distances,
  • a priority queue holding pairs \((\text{distance}, \text{vertex})\),
  • optionally, a visited/finalized marker to avoid decrease-key operations (common with “lazy” priority queues).

In contexts like min-cost flow, total runtime depends on how many times shortest paths are recomputed and how the surrounding algorithm limits the number of augmentations.

4 Correctness

4.1 Proof sketch: preservation of optimal paths

Consider any path \(P\) from \(s\) to \(v\). The difference between its original cost and its reduced cost is \(\pi(s)-\pi(v)\), a quantity independent of the interior of the path. Therefore, for two paths \(P_1,P_2\) from \(s\) to \(v\), \[ \text{cost}(P_1)\le \text{cost}(P_2) \quad\Longleftrightarrow\quad \text{reduced}(P_1)\le \text{reduced}(P_2). \] As a consequence, the set of shortest paths under reduced costs matches the set of shortest paths under original costs once the final distance is adjusted by the potential offset.

4.2 Proof sketch: nonnegativity implies Dijkstra applicability

Dijkstra’s correctness hinges on the nonnegativity of edge weights it relaxes. When reduced costs are nonnegative on relevant edges, the algorithm’s greedy step remains valid: extracting the smallest tentative reduced distance finalizes that value and prevents later discovery of shorter paths to that vertex.

Thus, if the maintained potentials guarantee reduced costs \(c'(u,v)\ge 0\) for edges that Dijkstra might traverse, the computed \(d'\) values are correct shortest reduced distances. Distance recovery then yields correct original shortest distances.

4.3 Edge cases and failure modes

Potential-related failure modes include:

  • Incorrect initialization that does not ensure the needed reduced-cost nonnegativity, leading to Dijkstra producing invalid results.
  • Graphs with reachable negative cycles under original costs. In such cases, shortest-path distances are undefined, and no reweighting scheme can restore a finite solution.
  • In min-cost flow residual networks, missing updates of potentials for unreachable vertices can break the intended invariant if later computations assume potentials were updated consistently.
  • Numeric issues (e.g., floating-point rounding) that produce small negative reduced costs due to imprecision; practical implementations often use tolerance thresholds or keep costs integral.

5 Integration with min-cost flow

5.1 Why repeated shortest paths are needed

Min-cost flow algorithms aim to send a fixed amount of flow from sources to sinks while minimizing total cost. A common strategy augments the current flow along paths in the residual graph that improve the objective at each step. The relevant improvement corresponds to sending additional flow along shortest augmenting paths in terms of residual edge costs.

Because augmentation changes residual capacities and costs, the shortest augmenting path may change after each step, motivating repeated shortest-path computations.

5.2 Maintaining potentials across augmentations

Residual edge costs can become negative as the algorithm progresses. Potentials are used to compute shortest paths in a reweighted residual graph where reduced costs are kept nonnegative.

Typically, after each shortest-path computation, potentials are updated using the distances found. These updated potentials are then reused for the next augmentation, ensuring that the next Dijkstra call is run on a reweighted graph where nonnegativity conditions are satisfied for reachable vertices.

This reuse is what yields efficiency: each augmentation can be handled with one fast shortest-path computation rather than a full negative-edge-capable recomputation.

During a shortest-path phase, some vertices may be unreachable from the current source set in the residual graph. For such vertices, distance values are undefined (or remain infinite). Potential updates are generally applied only to vertices whose distance is finite; unreachable vertices keep their previous potential values.

This selective update preserves the invariants needed for the next reduced-cost computation while avoiding propagation of meaningless values that would contaminate reduced edge costs elsewhere.

5.4 Termination and optimality in the surrounding algorithm

The integration with min-cost flow typically stops when no negative-cost (or otherwise improving) augmenting path exists in the residual network, depending on the algorithm’s formulation. The surrounding proof of optimality rests on standard min-cost flow optimality conditions, such as the absence of improving cycles/paths under reduced costs.

Dijkstra with potentials supports these conditions by ensuring that each augmentation step correctly identifies the shortest augmenting path in the residual network according to the current cost structure, without requiring slower all-negative-edge shortest-path methods.

6 Practical considerations

6.1 Choice of initial potentials

Initial potentials can be obtained in several ways:

  • If the graph’s original costs are nonnegative, setting \(\pi(v)=0\) suffices.
  • If negative edges exist but no negative cycles are reachable from the source, initial potentials can be set using shortest distances computed by Bellman–Ford. Using \(\pi(v)\) derived from these distances provides the needed reduced-cost nonnegativity for the first Dijkstra run.
  • In iterative algorithms (like min-cost flow), potentials from prior iterations often serve as a natural starting point.

The choice affects performance mainly through the cost of initialization and the likelihood that subsequent reduced costs remain well-behaved.

6.2 Numerical stability and integer/float costs

With integer costs, reduced costs remain exact under integer arithmetic if potentials are computed from integers (or from exact distance sums). With floating-point costs, round-off can lead to reduced costs slightly below zero even when theory predicts nonnegativity.

Implementations may address this by:

  • using an epsilon tolerance when checking reduced costs,
  • clamping small negative reduced costs to zero,
  • or maintaining potentials and distances in higher precision.

Stability requirements are especially important in min-cost flow, where many iterations can accumulate error.

6.3 Performance trade-offs vs alternative approaches

Compared with running Bellman–Ford each time, Dijkstra with potentials is typically faster when reduced costs are kept nonnegative and Dijkstra’s complexity dominates. Compared with fully reweighting via re-running negative-edge shortest paths each iteration, the potential update avoids redundant work.

However, if potentials are not maintained well or initialization is expensive, the benefit may shrink. In sparse graphs, the advantage of Dijkstra’s heap-based method is often substantial.

6.4 Implementation patterns (graph representation, priority queue)

Common implementation patterns include:

  • adjacency lists with edges storing endpoint and original cost,
  • computing reduced costs on the fly as \(c + \pi(u) - \pi(v)\),
  • using a “lazy” priority queue (push updates, ignore stale entries by checking against the current distance array),
  • storing distances as arrays initialized to infinity, updating only visited vertices.

For speed, reduced-cost computations are simple arithmetic, but care is needed to avoid mixing old and updated potentials during distance recovery or subsequent relaxations.

7 Examples and walkthroughs

7.1 Small graph example with negative original costs

Consider a directed graph with source \(s\) and edges:

  • \(s\to a\) with cost \(2\),
  • \(s\to b\) with cost \(5\),
  • \(b\to a\) with cost \(-4\),
  • \(a\to t\) with cost \(3\),
  • \(b\to t\) with cost \(1\).

The original shortest path from \(s\) to \(a\) is \(s\to b\to a\) with total cost \(5+(-4)=1\), even though it uses a negative edge. Using suitable potentials, the reduced graph can be made nonnegative so Dijkstra can compute the same shortest routes efficiently.

7.2 Step-by-step potential updates

Suppose initial potentials are chosen so that all reduced costs are nonnegative for edges reachable from \(s\). Running Dijkstra on reduced costs produces reduced distances \(d'\) to each vertex. After the run, potentials are updated using the computed distances so that the reweighted costs reflect the new shortest-path structure.

On the next iteration (if part of a larger algorithm), the maintained potentials ensure that reduced costs relevant to reachable edges remain nonnegative. This prevents reintroducing negative reduced edges and keeps Dijkstra applicable.

7.3 Min-cost flow example using the method

In a min-cost flow residual network, assume certain residual edges have negative costs representing potential improvements. Directly running Dijkstra would fail if negative costs remain.

With potentials, those residual costs are transformed into reduced costs. Dijkstra then finds the shortest augmenting path under reduced costs, and the surrounding algorithm augments flow along the corresponding residual edges. Potentials are updated so the next augmenting path search operates under the correct reweighted cost system.

This sequence continues until no improving augmenting path remains, at which point the flow is optimal for the given instance.

8.1 Johnson’s reweighting connection

The reweighting step closely resembles Johnson’s algorithm for all-pairs shortest paths with negative edges. Both use vertex potentials to eliminate negative reduced edge costs so that Dijkstra can be used safely.

In the present single-source and iterative settings, potentials are updated over time rather than computed once globally, but the underlying telescoping principle and reduced-cost construction are the same.

8.2 Successive shortest augmenting path variants

In min-cost flow, the “successive shortest augmenting path” family differs in how shortest paths are defined and how potentials are updated. Some variants maintain potentials to guarantee nonnegative reduced costs at every phase, enabling repeated Dijkstra calls. Others may occasionally run a negative-edge-capable algorithm to reestablish a valid potential state.

The choice is guided by graph structure and by the cost/capacity update pattern of the residual network.

8.3 Alternative priority-queue implementations

The method is compatible with different priority queue data structures:

  • binary heaps (\(O(m\log n)\)),
  • Fibonacci heaps (theoretical improvements in decrease-key settings),
  • pairing heaps and radix heaps (in special cases, such as integer keys with bounded range).

Since Dijkstra is often called many times in min-cost flow, practical implementations typically favor robust and fast heap structures, with lazy deletion often simplifying code and avoiding expensive decrease-key operations.

9 Limitations and when not to use

9.1 When reduced costs may not be nonnegative

If one cannot maintain potentials that keep reduced costs nonnegative on edges processed by Dijkstra, the algorithm loses its correctness guarantee. This can happen due to improper initialization, failure to update potentials consistently, or presence of negative cycles that invalidate shortest-path distances.

9.2 Requirements on graph structure and cost model

The approach assumes the underlying shortest-path problem is well-defined (no reachable negative cycles for relevant sources). It also assumes that the cost model and arithmetic are compatible with maintaining accurate reduced costs—especially when using floating-point numbers.

In residual networks, the method relies on consistent interpretation of which edges and costs correspond to the current reduced-cost graph at each phase.

9.3 Comparison to Bellman–Ford-based approaches

Bellman–Ford handles negative edges directly and can compute shortest paths even when reduced nonnegativity is not achieved. However, it is generally slower on large graphs and becomes impractical when shortest paths are required repeatedly, such as in min-cost flow.

Dijkstra with potentials offers a performance advantage when potentials can be maintained effectively, but Bellman–Ford remains a reliable fallback when nonnegativity cannot be guaranteed.