Longest path in a directed acyclic graph in Python
Dynamic programming over a topological order gives the heaviest path from a source in a DAG in O(n + m) time; it is defined only for acyclic graphs.
- File
dag_longest_path.py, 94 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/dag-longest-path/. The authors are listed in prov/K16C2B.jsonl.
from collections import deque
NEG_INF = float("-inf")
def topological_order(n: int, edges: list[tuple[int, int, float]]) -> list[int]:
"""Kahn's algorithm. Raise ValueError if the directed graph has a cycle."""
out: list[list[int]] = [[] for _ in range(n)]
indeg = [0] * n
for u, v, _ in edges:
out[u].append(v)
indeg[v] += 1
queue = deque(u for u in range(n) if indeg[u] == 0)
order: list[int] = []
while queue:
u = queue.popleft()
order.append(u)
for v in out[u]:
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)
if len(order) < n:
raise ValueError("the graph has a cycle, so longest paths are not defined")
return order
def dag_longest_path(
n: int, edges: list[tuple[int, int, float]], s: int
) -> tuple[list[float], list[int | None]]:
"""Longest path weights from s in a directed acyclic multigraph.
edges[i] = (u, v, w) is an arc u -> v of weight w; weights may be negative and
parallel arcs are allowed. Returns (dist, parent): dist[v] is the largest weight of
a path from s to v, or -inf if v is not reachable from s, and the parent pointers
give such a path. Raises ValueError if the graph has a cycle (a self-loop is one).
Time O(n + m), extra space O(n + m).
"""
order = topological_order(n, edges) # @line L1
out: list[list[tuple[int, float]]] = [[] for _ in range(n)]
for u, v, w in edges:
out[u].append((v, w))
dist: list[float] = [NEG_INF] * n # @line L2
parent: list[int | None] = [None] * n
dist[s] = 0 # @line L3
for u in order: # @line L4
if dist[u] == NEG_INF: # @line L5
continue
for v, w in out[u]: # @line L6
if dist[u] + w > dist[v]: # @line L7
dist[v] = dist[u] + w # @line L8
parent[v] = u
return dist, parent # @line L9
def path_to(parent: list[int | None], s: int, t: int) -> list[int]:
"""The vertices of the path from s to t given by the parent pointers."""
path = [t]
while path[-1] != s:
p = parent[path[-1]]
if p is None:
raise ValueError("t is not reachable from s")
path.append(p)
path.reverse()
return path
def longest_path_anywhere(n: int, edges: list[tuple[int, int, float]]) -> tuple[float, list[int]]:
"""The heaviest path of the whole DAG, from any vertex to any vertex.
A path of one vertex has weight 0, so the answer is at least 0 when n >= 1.
Same as dag_longest_path with every dist starting at 0 instead of -inf.
"""
if n == 0:
return 0, []
order = topological_order(n, edges)
out: list[list[tuple[int, float]]] = [[] for _ in range(n)]
for u, v, w in edges:
out[u].append((v, w))
dist: list[float] = [0] * n
parent: list[int | None] = [None] * n
for u in order:
for v, w in out[u]:
if dist[u] + w > dist[v]:
dist[v] = dist[u] + w
parent[v] = u
t = max(range(n), key=lambda v: dist[v])
path = [t]
while parent[path[-1]] is not None:
path.append(parent[path[-1]]) # type: ignore[arg-type]
path.reverse()
return dist[t], path
test_dag_longest_path.py 101 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/dag-longest-path/. The authors are listed in prov/K16C2B.jsonl.
import random
import pytest
from dag_longest_path import NEG_INF, dag_longest_path, longest_path_anywhere, path_to
EXAMPLE = [(0, 1, 3), (0, 2, 2), (1, 3, 4), (2, 3, 6), (2, 4, 1), (3, 5, 2), (4, 5, 5)]
def all_paths(n: int, edges: list[tuple[int, int, float]], s: int) -> list[tuple[float, list[int]]]:
"""Every path from s, with its weight, found by plain search. Exponential."""
out: list[list[tuple[int, float]]] = [[] for _ in range(n)]
for u, v, w in edges:
out[u].append((v, w))
result: list[tuple[float, list[int]]] = []
todo: list[tuple[float, list[int]]] = [(0, [s])]
while todo:
weight, path = todo.pop()
result.append((weight, path))
for v, w in out[path[-1]]:
assert v not in path # the graph is acyclic
todo.append((weight + w, path + [v]))
return result
def random_dag(rng: random.Random, n: int, m: int) -> list[tuple[int, int, float]]:
rank = list(range(n))
rng.shuffle(rank)
edges = []
for _ in range(m):
a, b = rng.sample(range(n), 2)
if rank[a] > rank[b]:
a, b = b, a
edges.append((a, b, rng.randint(-5, 9)))
return edges
def path_weight(edges: list[tuple[int, int, float]], path: list[int]) -> float:
best: dict[tuple[int, int], float] = {}
for u, v, w in edges:
best[(u, v)] = max(best.get((u, v), NEG_INF), w)
return sum(best[(path[i], path[i + 1])] for i in range(len(path) - 1))
def test_example() -> None:
dist, parent = dag_longest_path(6, EXAMPLE, 0)
assert dist == [0, 3, 2, 8, 3, 10]
assert path_to(parent, 0, 5) == [0, 2, 3, 5]
assert longest_path_anywhere(6, EXAMPLE) == (10, [0, 2, 3, 5])
def test_edge_cases() -> None:
assert dag_longest_path(1, [], 0) == ([0], [None])
# isolated and unreachable vertices keep -inf
dist, _ = dag_longest_path(3, [(1, 2, 4)], 0)
assert dist == [0, NEG_INF, NEG_INF]
# parallel arcs: the heavier one counts
assert dag_longest_path(2, [(0, 1, 1), (0, 1, 7)], 0)[0] == [0, 7]
# negative weights are allowed
assert dag_longest_path(3, [(0, 1, -2), (1, 2, -3), (0, 2, -9)], 0)[0] == [0, -2, -5]
assert longest_path_anywhere(0, []) == (0, [])
assert longest_path_anywhere(2, [(0, 1, -4)])[0] == 0
def test_cycles_rejected() -> None:
with pytest.raises(ValueError):
dag_longest_path(1, [(0, 0, 1)], 0) # a self-loop
with pytest.raises(ValueError):
dag_longest_path(3, [(0, 1, 1), (1, 2, 1), (2, 1, 1)], 0)
with pytest.raises(ValueError):
longest_path_anywhere(2, [(0, 1, 1), (1, 0, 1)])
def test_long_path() -> None:
n = 100_000
edges = [(i, i + 1, 1) for i in range(n - 1)]
dist, parent = dag_longest_path(n, edges, 0)
assert dist[-1] == n - 1
assert len(path_to(parent, 0, n - 1)) == n
def test_random_against_brute_force() -> None:
rng = random.Random(20261105)
for _ in range(800):
n = rng.randint(1, 7)
edges = random_dag(rng, n, rng.randint(0, 12)) if n > 1 else []
s = rng.randrange(n)
dist, parent = dag_longest_path(n, edges, s)
paths = all_paths(n, edges, s)
for v in range(n):
ws = [w for w, p in paths if p[-1] == v]
assert dist[v] == (max(ws) if ws else NEG_INF)
if ws:
p = path_to(parent, s, v)
assert p[0] == s and path_weight(edges, p) == dist[v]
best = max(w for t in range(n) for w, _ in all_paths(n, edges, t))
weight, p = longest_path_anywhere(n, edges)
assert weight == best and path_weight(edges, p) == best
What the next level needs
- the tests did not run in this build
Read the full page about Longest path in a directed acyclic graph