Suurballe's Algorithm, in depth: two disjoint shortest paths with two Dijkstra runs, reduced weights, cancellation and network protection

The problem, stated precisely

The input is a directed graph G with n nodes and m arcs, a non-negative weight w(u, v) on every arc, a source s and a target t. We want two paths from s to t that share no arc and whose total weight is as small as possible. The paths may pass through the same node. If they must not, that is the vertex-disjoint version, which reduces to this one with a small graph change described later.

An undirected graph becomes two opposite arcs per edge. With positive weights, an optimal answer never crosses one physical edge in both directions; with zero-weight edges, check the result for such a pair.

We minimise the sum because that is what you pay when both paths are leased, and because it is tractable. Minimising the longer path, or capping both, is NP-hard in general, like constrained shortest path.

Why the greedy method fails

Look at the graph in the figure. The shortest s-t path is s-a-b-t with cost 3. Remove its three arcs. The only arc left out of s is s-c, and from c you reach b, but b's only outgoing arc was b-t, which is gone. The greedy method reports that no second path exists.

Yet a pair exists: s-a-d-t and s-c-b-t, each of cost 5. The shortest path used the middle arc a-b, and that arc is exactly the link the two good routes need to avoid. Greedy commits to it and cannot take it back. When greedy does find a second path, the same mistake shows up as a pair that costs more than the optimum.

The two ideas: residual arcs and reduced weights

The fix comes from network flow. Think of the two paths as two units of flow from s to t, each arc carrying at most one unit. After you route the first unit along P1, the residual graph lets a second unit push back along any arc of P1, which means taking it out of P1. If the second path P2 uses the reversed arc b-a, the two searches together route zero units over a-b. The arc cancels, and the remaining arcs regroup into two different paths. This is the same augmenting-path idea as Ford-Fulkerson, with costs added.

Reversed arcs carry negative cost, which Dijkstra cannot handle. Suurballe's second idea removes them. Let d(v) be the shortest distance from s to v found in the first pass, and define the reduced weight w'(u, v) = w(u, v) + d(u) - d(v). The triangle inequality d(v) ≤ d(u) + w(u, v) makes every w' non-negative. Every arc on a shortest path gets w' = 0, so reversing it at cost 0 is consistent. For any s-t path, the reduced cost equals the original cost minus d(t), a constant, so shortest paths stay shortest. This is the potential trick also used in Johnson's algorithm.

The algorithm in five steps

The full algorithm has five steps.

1. Run Dijkstra from s on the original weights. Record d(v) for every node and the shortest path P1 to t. If t is unreachable, stop.
2. Build the residual graph. Every arc gets its reduced weight w'(u, v) = w(u, v) + d(u) - d(v). Every arc of P1 is replaced by its reverse, with weight 0. Drop nodes that were unreachable in step 1.
3. Run Dijkstra from s on the residual graph to find P2. If t is unreachable, no pair of arc-disjoint paths exists, by the max-flow min-cut argument: some single arc separates s from t.
4. Take the union of the arcs of P1 and P2. Wherever P2 used the reverse of a P1 arc, delete both. What remains is a set of arcs with exactly two more leaving s than entering it, and two more entering t than leaving it.
5. Walk from s along unused arcs until you reach t, twice. Those walks are the two paths. Any arcs left over form cycles of zero cost, which you discard.

The total cost is 2·d(t) + d'(t), where d'(t) is the second-pass distance to t.

A full trace on the trap graph

Trace it on the trap graph. The first Dijkstra gives d(s) = 0, d(a) = 1, d(b) = 2, d(t) = 3, d(c) = 3 and d(d) = 4, and P1 = s-a-b-t. Now compute the reduced weights.

The second Dijkstra starts at s. Its only way out is s-c at 0, then c-b at 2, then the reversed arc b-a at 0, then a-d at 0, then d-t at 2. So P2 = s-c-b-a-d-t with reduced cost 4. Its original cost is 4 + d(t) = 7, which is 3 + 1 - 1 + 3 + 1: the -1 is the saving from cancelling a-b. The total is 3 + 7 = 10.

Now cancel. P1 used a-b and P2 used b-a, so both go. The arcs left are s-a, a-d, d-t, s-c, c-b and b-t. Walking from s gives s-a-d-t and s-c-b-t, each of cost 5, the optimal pair.

A tested implementation

The implementation below keeps arcs in a list and refers to them by index. That matters. With parallel arcs, or with an arc a-b and a separate arc b-a in the original graph, a dictionary keyed by node pairs would confuse the reversed P1 arc with a real one and cancel the wrong thing.

import heapq
from collections import defaultdict

def dijkstra(n, arcs, out, src, weight):
    dist, via = [float("inf")] * n, [None] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for e in out[u]:
            v = arcs[e][1]
            nd = d + weight(e)
            if nd < dist[v]:
                dist[v], via[v] = nd, e
                heapq.heappush(heap, (nd, v))
    return dist, via

def path_arcs(arcs, via, s, t):
    p, v = [], t
    while v != s:
        p.append(via[v])
        v = arcs[via[v]][0]
    return p[::-1]

def suurballe(n, edges, s, t):
    """edges: list of (u, v, w), w >= 0. Returns (cost, [path1, path2]) or None."""
    arcs, out = list(edges), defaultdict(list)
    for i, (u, v, w) in enumerate(arcs):
        out[u].append(i)

    d, via = dijkstra(n, arcs, out, s, lambda e: arcs[e][2])     # pass 1
    if d[t] == float("inf"):
        return None
    p1 = set(path_arcs(arcs, via, s, t))

    res, rout = [], defaultdict(list)                            # residual graph
    for i, (u, v, w) in enumerate(arcs):
        if d[u] == float("inf") or d[v] == float("inf"):
            continue
        if i in p1:
            res.append((v, u, 0, i, -1))                         # reversed P1 arc
        else:
            res.append((u, v, w + d[u] - d[v], i, +1))           # reduced weight
        rout[res[-1][0]].append(len(res) - 1)

    d2, via2 = dijkstra(n, res, rout, s, lambda e: res[e][2])     # pass 2
    if d2[t] == float("inf"):
        return None
    used = set(p1)
    for e in path_arcs(res, via2, s, t):
        orig, sign = res[e][3], res[e][4]
        if sign < 0:
            used.discard(orig)                                   # cancel
        else:
            used.add(orig)

    nxt = defaultdict(list)
    for i in used:
        nxt[arcs[i][0]].append(i)
    paths = []
    for _ in range(2):                                           # decompose
        node, path = s, [s]
        while node != t:
            node = arcs[nxt[node].pop()][1]
            path.append(node)
        paths.append(path)
    return 2 * d[t] + d2[t], paths

# s=0 a=1 b=2 t=3 c=4 d=5
E = [(0,1,1), (1,2,1), (2,3,1), (1,5,3), (5,3,1), (0,4,3), (4,2,1)]
print(suurballe(6, E, 0, 3))   # (10, [[0, 4, 2, 3], [0, 1, 5, 3]])

Test it against brute force: enumerate every disjoint pair of arc-simple s-t walks in random graphs of up to seven nodes. This code passed 3,000 such graphs, including zero weights, parallel arcs and opposite arc pairs.

Why it is optimal, and how fast

Why is the result optimal? Two arc-disjoint paths are a flow of value 2 with unit capacities, and their total cost is the flow's cost. Successive shortest paths is a standard min-cost flow method: start with zero flow, and repeatedly push one unit along the cheapest path in the residual graph. It returns a minimum-cost flow as long as the residual graph never contains a negative cycle, and the potentials ensure that. Suurballe's algorithm is exactly two rounds of this method, with the potentials from round one making round two safe for Dijkstra. The max-flow side of the story, including why one arc separating s and t is the only reason a pair can fail to exist, is in the max-flow min-cut theorem.

The cost is two Dijkstra runs plus linear work, so O((m + n) log n) with a binary heap. Enumerating k shortest paths and filtering for disjointness, by contrast, can need a huge number of candidates.

Variants

Vertex-disjoint paths. Split every node v other than s and t into v_in and v_out joined by a single arc of weight 0. Arcs that entered v now enter v_in, and arcs that left v now leave v_out. A node can then carry only one path, because its internal arc can carry only one unit. Run the same algorithm. For physical networks this is usually what you want, since a router failure takes out every link through it.

k paths. Repeat the residual step k - 1 times, updating the potentials after each round by adding the new distances. Each round costs one Dijkstra. This is successive shortest paths with k units.

All targets at once. Suurballe and Tarjan (1984) find disjoint pairs from s to every node in about the time of one shortest-path run.

Where it is used, and where the model breaks

The main users are network planners. In 1+1 protection, traffic is sent on both paths and the receiver switches when one fails. In 1:1 protection, a backup path is reserved and used only after a failure. Either way you want the cheapest disjoint pair. The same calculation picks two physically separate uplinks for a data centre and checks whether a design has any disjoint pair at all.

Two warnings apply. First, disjoint in the graph is not always disjoint in the ground. Two fibres that are separate arcs can share a trench, a conduit or a building. Operators model this with shared risk link groups (SRLGs), and the cheapest SRLG-disjoint pair is NP-hard in general, so teams use heuristics or integer programming. Second, the optimal pair minimises the sum, so it may pair a very short path with a much longer one. If the backup must meet a latency budget, check it explicitly.

Implementation bugs

These are the bugs that most often break real implementations.

• Negative weights. The first pass is Dijkstra, so every input weight must be non-negative. If you subtract a discount from some links, use Bellman-Ford for pass one or shift the weights.
• Node-pair keys. Storing arcs in a map keyed by (u, v) breaks on parallel arcs and on graphs that already contain v-u. Use arc identifiers, as the code does.
• Forgetting to cancel. Returning P1 and P2 directly gives two walks that share an arc in opposite directions. The cancellation step is not optional.
• Unreachable potentials. Nodes with d(v) = infinity produce infinity minus infinity when reweighting. Drop them before building the residual graph.
• Floating-point potentials. Rounding can give reduced weights of -1e-15; use integer weights.
• Decomposition cycles. With zero-weight arcs, the union can contain a cycle. Walk from s to t and ignore leftover arcs instead of assuming every arc lies on one of the two paths.

Trade-offs

What to do next

1. Run the code on the trap graph and confirm it returns 10.
2. Write a brute-force checker and test thousands of small random graphs, with zero weights and parallel arcs.
3. Add node splitting and check the vertex-disjoint answer on a graph where two paths would otherwise share a node.
4. Extend the function to k paths and confirm the cost never decreases as k grows.
5. Take a real topology, such as your office or cloud network diagram, and list the arcs every pair shares when SRLGs are taken into account.
6. Review Dijkstra's algorithm if any step of the heap logic felt unclear, because both passes depend on it.