Gabow's scaling algorithm in Python
Bit-scaling SSSP for integer weights. Each bit costs one bucket-based Dijkstra pass, so nonnegative weights take O(m log N) time; the negative-weight versions reach O(sqrt(n) m log(nN)).
- File
gabow_scaling_sssp.py, 67 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-scaling-sssp/. The authors are listed in prov/N36TQW.jsonl.
import math
INF = math.inf
def gabow_scaling(
adj: list[list[tuple[int, int]]], s: int, trace: list | None = None
) -> tuple[list, list]:
"""Single-source shortest paths by bit scaling, for nonnegative integer weights.
The graph has the vertices 0 .. n-1; adj[u] lists the edges (v, w) out of u.
Every weight must be an integer >= 0, or ValueError is raised. Returns (d,
parent): d[v] is the distance from s (math.inf if v is unreachable) and parent[v]
the previous vertex on a shortest path (None for s and unreachable vertices).
If trace is a list, the labels after each scale are appended to it.
Time O((n + m) log N) for the largest weight N, extra space O(n).
"""
n = len(adj)
top = 0
for u in range(n):
for _, w in adj[u]:
if not isinstance(w, int) or w < 0:
raise ValueError("weights must be nonnegative integers")
top = max(top, w)
b = top.bit_length() # @line L1
d: list = [INF] * n # scale 0: all weights are 0
parent: list = [None] * n
d[s] = 0
stack = [s]
while stack:
u = stack.pop()
for v, _ in adj[u]:
if d[v] == INF:
d[v], parent[v] = 0, u
stack.append(v)
if trace is not None:
trace.append(list(d))
for i in range(1, b + 1): # @line L2
shift = b - i
delta = [INF] * n
par: list = [None] * n
delta[s] = 0
buckets: list[list[int]] = [[] for _ in range(n)]
buckets[0].append(s)
done = [False] * n
for level in range(n): # Dial's algorithm on the reduced lengths
for u in buckets[level]:
if done[u] or delta[u] != level:
continue
done[u] = True
for v, w in adj[u]:
wi = w >> shift # @line L3
r = wi + 2 * d[u] - 2 * d[v] # @line L4
nd = level + r
if nd < delta[v] and nd < n: # @line L5
delta[v], par[v] = nd, u
buckets[nd].append(v)
for v in range(n):
if d[v] != INF:
d[v] = 2 * d[v] + delta[v] # @line L6
parent = par
if trace is not None:
trace.append(list(d))
return d, parent # @line L7
test_gabow_scaling_sssp.py 119 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-scaling-sssp/. The authors are listed in prov/N36TQW.jsonl.
import math
import random
import pytest
from gabow_scaling_sssp import gabow_scaling
INF = math.inf
# s=0, a=1, b=2, c=3
EXAMPLE = [(0, 1, 5), (0, 2, 3), (2, 1, 1), (1, 3, 2), (2, 3, 7)]
def build(n, edges):
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
return adj
def bellman_ford(adj, s):
"""Independent oracle: distances from s, or None if a negative cycle is reachable."""
n = len(adj)
d = [INF] * n
d[s] = 0
for _ in range(n - 1):
for u in range(n):
for v, w in adj[u]:
if d[u] + w < d[v]:
d[v] = d[u] + w
for u in range(n):
for v, w in adj[u]:
if d[u] + w < d[v]:
return None
return d
def check_tree(adj, s, d, parent):
for v in range(len(adj)):
if v == s or d[v] == INF:
assert parent[v] is None
continue
u = parent[v]
assert d[v] == d[u] + min(w for x, w in adj[u] if x == v)
def test_example() -> None:
trace = []
adj = build(4, EXAMPLE)
d, parent = gabow_scaling(adj, 0, trace)
assert d == [0, 4, 3, 6]
assert parent == [None, 2, 0, 1]
assert trace == [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 2], [0, 4, 3, 6]]
def test_unreachable_vertices_stay_infinite() -> None:
adj = build(4, [(0, 1, 3), (2, 3, 1), (3, 0, 1)])
d, parent = gabow_scaling(adj, 0)
assert d == [0, 3, INF, INF] and parent == [None, 0, None, None]
def test_all_zero_weights() -> None:
adj = build(3, [(0, 1, 0), (1, 2, 0), (2, 0, 0)])
d, parent = gabow_scaling(adj, 0)
assert d == [0, 0, 0] and parent == [None, 0, 1]
def test_single_vertex() -> None:
assert gabow_scaling([[]], 0) == ([0], [None])
def test_negative_weight_is_rejected() -> None:
with pytest.raises(ValueError):
gabow_scaling(build(2, [(0, 1, -1)]), 0)
def test_negative_cycle_is_rejected() -> None:
# every negative cycle has a negative edge, so it is rejected up front
adj = build(3, [(0, 1, 2), (1, 2, -3), (2, 1, 1)])
with pytest.raises(ValueError):
gabow_scaling(adj, 0)
def test_non_integer_weight_is_rejected() -> None:
with pytest.raises(ValueError):
gabow_scaling(build(2, [(0, 1, 1.5)]), 0)
def test_large_weights() -> None:
adj = build(3, [(0, 1, 10**12), (1, 2, 10**12 + 7), (0, 2, 3 * 10**12)])
d, _ = gabow_scaling(adj, 0)
assert d == [0, 10**12, 2 * 10**12 + 7]
def test_each_scale_is_the_scaled_distance() -> None:
rng = random.Random(7)
adj = build(6, [(rng.randrange(6), rng.randrange(6), rng.randint(0, 50)) for _ in range(15)])
trace = []
d, _ = gabow_scaling(adj, 0, trace)
b = max([w for row in adj for _, w in row] + [0]).bit_length()
for i, labels in enumerate(trace):
scaled = [[(v, w >> (b - i)) for v, w in row] for row in adj]
assert labels == bellman_ford(scaled, 0)
def test_random_against_bellman_ford() -> None:
rng = random.Random(1985)
for _ in range(800):
n = rng.randint(1, 9)
top = rng.choice([1, 3, 20, 1000, 10**6])
edges = [(rng.randrange(n), rng.randrange(n), rng.randint(0, top))
for _ in range(rng.randint(0, 3 * n))]
adj = build(n, edges)
s = rng.randrange(n)
d, parent = gabow_scaling(adj, s)
assert d == bellman_ford(adj, s)
check_tree(adj, s, d, parent)
What the next level needs
- the tests did not run in this build