D'Esopo-Pape algorithm in Python
Single-source shortest path algorithm that uses a deque, inserting nodes at the front or back depending on whether they were seen before.
- File
desopo_pape_algorithm.py, 47 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/desopo-pape-algorithm/. The authors are listed in prov/5Q4Y55.jsonl.
import math
from collections import deque
INF = math.inf
NEVER, IN_QUEUE, LEFT = 0, 1, 2
def desopo_pape(
adj: list[list[tuple[int, float]]], s: int
) -> tuple[list[float], list[int | None]] | None:
"""Single-source shortest paths by the D'Esopo-Pape deque rule.
The graph has the vertices 0 .. n-1; adj[u] lists the edges (v, w) out of u, and
weights may be negative. Returns (d, parent) with d[v] = math.inf for vertices
not reachable from s, or None if a cycle of negative weight is reachable from s.
A vertex whose label drops is put at the back of the deque the first time and at
the front if it has been in the deque before. To stop on a negative cycle, the
number of edges of the walk behind each label is kept; it reaches n only if a
negative cycle is reachable. Exponential time in the worst case.
"""
n = len(adj)
d = [INF] * n # @line L1
parent: list[int | None] = [None] * n
hops = [0] * n
state = [NEVER] * n
d[s] = 0 # @line L2
q = deque([s])
state[s] = IN_QUEUE
while q: # @line L3
u = q.popleft() # @line L4
state[u] = LEFT
for v, w in adj[u]: # @line L5
if d[u] + w < d[v]: # @line L6
d[v] = d[u] + w # @line L7
parent[v] = u
hops[v] = hops[u] + 1
if hops[v] >= n:
return None
if state[v] == NEVER: # @line L8
q.append(v)
elif state[v] == LEFT: # @line L9
q.appendleft(v)
state[v] = IN_QUEUE
return d, parent # @line L10
test_desopo_pape_algorithm.py 84 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/desopo-pape-algorithm/. The authors are listed in prov/5Q4Y55.jsonl.
import math
import random
from desopo_pape_algorithm import desopo_pape
INF = math.inf
# s=0, a=1, b=2, c=3, d=4
EXAMPLE = [[(1, 2), (2, 6), (3, 7)], [(2, 3), (4, 8)], [(4, 1)], [(1, -6)], []]
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 or v == s
continue
u = parent[v]
assert d[v] == d[u] + min(w for x, w in adj[u] if x == v)
def test_example() -> None:
d, parent = desopo_pape(EXAMPLE, 0)
assert d == [0, 1, 4, 7, 5]
assert parent == [None, 3, 1, 0, 2]
def test_unreachable() -> None:
adj = [[(1, -2)], [], [(0, 1), (1, 1)]]
d, parent = desopo_pape(adj, 0)
assert d == [0, -2, INF] and parent[2] is None
def test_negative_cycle() -> None:
adj = [[(1, 1)], [(2, -3)], [(1, 1), (3, 0)], []]
assert desopo_pape(adj, 0) is None
assert desopo_pape([[(0, -1)]], 0) is None
def test_negative_cycle_not_reachable() -> None:
adj = [[(1, 4)], [], [(3, -2)], [(2, 1)]]
assert desopo_pape(adj, 0) == ([0, 4, INF, INF], [None, 0, None, None])
def test_zero_cycle_terminates() -> None:
adj = [[(1, 0)], [(2, 0)], [(0, 0), (3, -1)], []]
d, _ = desopo_pape(adj, 0)
assert d == [0, 0, 0, -1]
def test_random_against_bellman_ford() -> None:
rng = random.Random(1974)
for _ in range(800):
n = rng.randint(1, 8)
adj = [[] for _ in range(n)]
low = rng.choice([0, -1, -3, -6])
for _ in range(rng.randint(0, 3 * n)):
adj[rng.randrange(n)].append((rng.randrange(n), rng.randint(low, 9)))
s = rng.randrange(n)
want = bellman_ford(adj, s)
got = desopo_pape(adj, s)
if want is None:
assert got is None
else:
assert got is not None and got[0] == want
check_tree(adj, s, got[0], got[1])
What the next level needs
- the tests did not run in this build