ALT algorithm in Python
A* with landmark-based lower bounds derived from the triangle inequality.
- File
alt_algorithm.py, 104 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/alt-algorithm/. The authors are listed in prov/DBXZ34.jsonl.
import heapq
import math
INF = math.inf
def _dijkstra(adj: list[list[tuple[int, float]]], s: int) -> list[float]:
"""Plain Dijkstra with a lazy-deletion heap; distances from s."""
d = [INF] * len(adj)
d[s] = 0
heap = [(0, s)]
while heap:
du, u = heapq.heappop(heap)
if du > d[u]:
continue
for v, w in adj[u]:
if du + w < d[v]:
d[v] = du + w
heapq.heappush(heap, (d[v], v))
return d
def alt_preprocess(
adj: list[list[tuple[int, float]]], landmarks: list[int]
) -> list[tuple[list[float], list[float]]]:
"""For each landmark L, return (dist from L, dist to L).
The graph has the vertices 0 .. n-1; adj[u] lists the edges (v, w) out of u.
Precondition: every weight is nonnegative (a ValueError is raised otherwise).
Time O(k (n + m) log m) for k landmarks, space O(k n).
"""
n = len(adj)
radj: list[list[tuple[int, float]]] = [[] for _ in range(n)]
for u in range(n):
for v, w in adj[u]:
if w < 0:
raise ValueError("ALT needs nonnegative weights")
radj[v].append((u, w))
tables = []
for lm in landmarks:
tables.append((_dijkstra(adj, lm), _dijkstra(radj, lm))) # @line L1
return tables
def _lower_bound(tables, v: int, t: int) -> float:
"""Landmark lower bound on dist(v, t); INF means that v cannot reach t."""
h = 0
for frm, to in tables:
# dist(v, t) >= dist(v, L) - dist(t, L)
if to[t] < INF:
h = max(h, to[v] - to[t])
# dist(v, t) >= dist(L, t) - dist(L, v)
if frm[v] < INF:
h = max(h, frm[t] - frm[v])
return h
def alt_query(
adj: list[list[tuple[int, float]]],
tables: list[tuple[list[float], list[float]]],
s: int,
t: int,
) -> tuple[float, list[int] | None, int]:
"""Return (dist, path, scans): the distance from s to t, a shortest path, and
the number of vertices scanned.
tables comes from alt_preprocess on the same graph. If t is not reachable from s,
returns (math.inf, None, scans). This is A* search with the landmark lower bound
as heuristic, which is consistent, so each vertex is scanned at most once.
"""
n = len(adj)
h: list[float | None] = [None] * n # computed on first touch
def bound(v: int) -> float:
if h[v] is None:
h[v] = _lower_bound(tables, v, t) # @line L2
return h[v]
g = [INF] * n
parent: list[int | None] = [None] * n
done = [False] * n
g[s] = 0 # @line L3
heap = [(bound(s), s)] if bound(s) < INF else []
scans = 0
while heap: # @line L4
_, u = heapq.heappop(heap) # @line L5
if done[u]:
continue
done[u] = True
scans += 1
if u == t: # @line L6
path = [t]
while path[-1] != s:
path.append(parent[path[-1]])
return g[t], path[::-1], scans
for v, w in adj[u]: # @line L7
if bound(v) < INF and g[u] + w < g[v]: # @line L8
g[v] = g[u] + w # @line L9
parent[v] = u
heapq.heappush(heap, (g[v] + bound(v), v))
return INF, None, scans # @line L10
test_alt_algorithm.py 107 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/alt-algorithm/. The authors are listed in prov/DBXZ34.jsonl.
import math
import random
import pytest
from alt_algorithm import alt_preprocess, alt_query
INF = math.inf
# s=0, a=1, b=2, t=3, x=4, y=5, z=6, l=7; every edge goes both ways
EXAMPLE_EDGES = [(0, 1, 2), (1, 2, 2), (2, 3, 2), (0, 4, 1), (4, 5, 1), (5, 6, 1), (3, 7, 1)]
def undirected(n, edges):
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
return adj
def bellman_ford(adj, s):
"""Independent oracle: n - 1 rounds of relaxing every edge."""
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
return d
def path_weight(adj, p):
return sum(min(w for v, w in adj[a] if v == b) for a, b in zip(p, p[1:]))
def test_example_with_landmark() -> None:
adj = undirected(8, EXAMPLE_EDGES)
assert alt_query(adj, alt_preprocess(adj, [7]), 0, 3) == (6, [0, 1, 2, 3], 4)
def test_example_without_landmarks_is_dijkstra() -> None:
adj = undirected(8, EXAMPLE_EDGES)
assert alt_query(adj, alt_preprocess(adj, []), 0, 3) == (6, [0, 1, 2, 3], 7)
def test_source_equals_target() -> None:
adj = undirected(8, EXAMPLE_EDGES)
assert alt_query(adj, alt_preprocess(adj, [6]), 5, 5) == (0, [5], 1)
def test_unreachable_target() -> None:
# 0 -> 1 -> 2, and 3 -> 0; vertex 3 is unreachable from 0
adj = [[(1, 1)], [(2, 1)], [], [(0, 1)]]
for lms in ([], [0], [2], [3], [1, 3]):
tables = alt_preprocess(adj, lms)
assert alt_query(adj, tables, 0, 3)[:2] == (INF, None)
assert alt_query(adj, tables, 2, 0)[:2] == (INF, None)
assert alt_query(adj, tables, 3, 2)[:2] == (3, [3, 0, 1, 2])
def test_landmark_proves_unreachability_without_search() -> None:
# t=2 reaches the landmark 3, s=0 does not, so the bound at s is infinite
adj = [[(1, 1)], [], [(3, 1)], []]
assert alt_query(adj, alt_preprocess(adj, [3]), 0, 2) == (INF, None, 0)
def test_negative_weight_rejected() -> None:
with pytest.raises(ValueError):
alt_preprocess([[(1, -1)], []], [0])
def test_negative_cycle_rejected() -> None:
with pytest.raises(ValueError):
alt_preprocess([[(1, 1)], [(0, -2)]], [])
def test_zero_weights_and_parallel_edges() -> None:
adj = [[(1, 0), (1, 5), (2, 4)], [(2, 0)], [(0, 0)]]
d, p, _ = alt_query(adj, alt_preprocess(adj, [1, 2]), 0, 2)
assert d == 0 and p == [0, 1, 2]
def test_random_against_bellman_ford() -> None:
rng = random.Random(2005)
for _ in range(600):
n = rng.randint(1, 9)
adj = [[] for _ in range(n)]
for _ in range(rng.randint(0, 3 * n)):
adj[rng.randrange(n)].append((rng.randrange(n), rng.randint(0, 9)))
lms = rng.sample(range(n), rng.randint(0, min(3, n)))
tables = alt_preprocess(adj, lms)
s = rng.randrange(n)
ref = bellman_ford(adj, s)
for t in range(n):
d, p, scans = alt_query(adj, tables, s, t)
assert d == ref[t]
if d == INF:
assert p is None
else:
assert p[0] == s and p[-1] == t and path_weight(adj, p) == d
# a consistent heuristic never scans a vertex twice
assert scans <= n
What the next level needs
- the tests did not run in this build