Dynamic programming on DAGs

In a directed acyclic graph, the longest path from a start node can be found in linear time: take the nodes in a topological order, and give each one the best total over the edges that reach it. A topological order puts every edge’s start before its end, so when a node’s turn comes, every route into it has already been scored. The same pass counts the routes, adds up durations into finish times, or finds shortest paths with negative weights. In a graph with cycles none of this works, and finding a longest simple path is NP-hard.

Two problems: the best trail and the number of trails

A hill park has n junctions, numbered 0 to n − 1, and one-way trails (u, v, w): the trail runs downhill from u to v, and its view score is w, from 1 to 10,000. Because every trail goes downhill, no route can return to a junction. Limits: up to 100,000 junctions and 200,000 trails.

Problem A. Return the highest total view score of a route from junction s to junction t, and the route, or −1 if t cannot be reached.

Problem B. Return the number of different routes from s to t, modulo 1,000,000,007.

In the park of the diagram, from the Summit (0) to the Gate (5), the best route scores 16 through the Old Fort and the Waterfall, and 4 routes exist in all. From the Gate to the Summit nothing is reachable: −1, and 0 routes. A junction to itself scores 0, with 1 route.

The brute force: walk every route

Walk every route from s with a stack, keep the best total that reaches t, and count the routes:

"""The brute force: walk every route from the summit to the gate, keeping the best score and counting the routes."""

JUNCTIONS = ["Summit", "Pine Ridge", "Old Fort", "Waterfall", "Tea Stall", "Gate"]
TRAILS = [(0, 1, 4), (0, 2, 2), (1, 3, 5), (2, 3, 8), (1, 4, 3), (2, 4, 7), (3, 5, 6), (4, 5, 1)]  # (from, to, view)


def every_route(n, trails, s, t):
    """The best total and its route, the number of routes, and the number of trail steps walked."""
    out = [[] for _ in range(n)]
    for u, v, w in trails:
        out[u].append((v, w))
    best, best_route, routes, steps = -1, [], 0, 0
    stack = [(s, 0, [s])]
    while stack:
        u, total, route = stack.pop()
        if u == t:
            routes += 1
            if total > best:
                best, best_route = total, route
            continue
        for v, w in out[u]:
            steps += 1
            stack.append((v, total + w, route + [v]))
    return best, best_route, routes, steps


best, route, routes, steps = every_route(6, TRAILS, 0, 5)
print(f"best view score {best}: {' -> '.join(JUNCTIONS[j] for j in route)}; {routes} routes in all")

out = {u: max((w, v) for a, v, w in TRAILS if a == u) for u in range(5)}  # the most scenic trail out of each junction
u, total, greedy = 0, 0, [0]
while u != 5:
    w, u = out[u]
    total += w
    greedy.append(u)
print(f"always the most scenic next trail: {total}, {' -> '.join(JUNCTIONS[j] for j in greedy)}")

print("\nA ladder of k levels, two junctions each, every junction joined to both of the next level:")
for k in (4, 8, 12, 16):
    trails = [(0, 1, 1), (0, 2, 1)]
    for level in range(k - 1):
        a, b = 1 + 2 * level, 2 + 2 * level
        trails += [(a, a + 2, 1), (a, b + 2, 1), (b, a + 2, 1), (b, b + 2, 1)]
    gate = 2 * k + 1
    trails += [(2 * k - 1, gate, 1), (2 * k, gate, 1)]
    best, route, routes, steps = every_route(gate + 1, trails, 0, gate)
    print(f"  {k:2} levels, {gate + 1:2} junctions: {routes:>6,} routes, {steps:>7,} trail steps walked")

best view score 16: Summit -> Old Fort -> Waterfall -> Gate; 4 routes in all
always the most scenic next trail: 15, Summit -> Pine Ridge -> Waterfall -> Gate

A ladder of k levels, two junctions each, every junction joined to both of the next level:
   4 levels, 10 junctions:     16 routes,      46 trail steps walked
   8 levels, 18 junctions:    256 routes,     766 trail steps walked
  12 levels, 26 junctions:  4,096 routes,  12,286 trail steps walked
  16 levels, 34 junctions: 65,536 routes, 196,606 trail steps walked

Walking always along the most scenic next trail gives 15, not 16: a 4-point trail to Pine Ridge looks better than 2 to the Old Fort, which leads on to a trail of 8. On a ladder of junctions, two a level with every junction joined to both of the next level, the routes double each level: 65,536 for 16 levels, and 2^49,999 for the 100,000 junctions the limits allow.

What to notice

The best total of a route ending at v depends only on the best totals of routes ending at the junctions that have a trail to v. In a graph without cycles, a topological order finishes all of those first. Four techniques follow:

• Relaxing each trail in topological order gives the longest, or the shortest, path from s.
• A route count adds up the counts of a junction’s predecessors, modulo 1,000,000,007.
• Parent pointers record the best predecessor of each junction, so the route can be rebuilt backwards.
• Memoised recursion computes the same values top-down, working each junction out once.

Longest paths from s in topological order, step by step Pro: opens with a Pro, Premium or Ultimate pass