Shortest paths in DAGs

When a directed graph has no cycles (a DAG), shortest routes need neither a heap nor many rounds. Put the vertices in topological order (GRPH-5) and relax each edge once. Negative weights are fine, and the longest route is just as easy.

Relax in topological order

GRPH-5 showed that a DAG has a topological order: a list of its vertices in which every edge goes from an earlier vertex to a later one. GRPH-5 also said that this order is the order in which a DP table can be filled (DYNP-3). Here the DP is the shortest time to each vertex:

Every u in the rule comes before v in the order. So going through the vertices in order, and relaxing each vertex’s edges out, offers every route to v before v’s own edges are used.

import math
from collections import deque

def dag_shortest(n, edges, s):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v, w in edges:
        adj[u].append((v, w))
        indeg[v] += 1
    order = []                     # Kahn's method, GRPH-5
    q = deque(v for v in range(n) if indeg[v] == 0)
    while q:
        u = q.popleft()
        order.append(u)
        for v, w in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    dist = [math.inf] * n
    dist[s] = 0
    for u in order:
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Why one pass is enough

Take any vertex v and a shortest route to it, s = v₀, v₁, …, v_k = v. The edges of the route go forward in the order, so v₀, v₁, … come in the order in that sequence. When v_i is handled, its value is already exact (by induction: the edge from v_i−1 was relaxed earlier, when v_i−1 already had its exact value), and relaxing v_i → v_i+1 gives v_i+1 its exact value. This is lesson 4’s argument with all its rounds folded into one: Bellman–Ford in topological order needs just one round.

Nothing in the proof needs weights to be 0 or more, so negative weights are fine. There can be no negative cycle, because there is no cycle at all. Cost: the order costs O(V + E), and the pass relaxes each edge once, so O(V + E), faster than Dijkstra. Vertices before s in the order keep ∞, and their edges change nothing.

Longest paths

In a general graph the longest simple route is NP-hard (lesson 1). In a DAG it is easy: there are no cycles to go round, so use the same pass with max instead of min (and −∞ instead of ∞), or flip the sign of every weight and find the shortest route. The second variant of the figure does this.

The critical path. In a project, tasks are vertices with durations, and an edge u → v says u must finish before v starts. The earliest moment the project can end is the longest route through the DAG, and the tasks on that route are the critical path: any delay there delays everything. GRPH-5 counted the longest chain of tasks; this is the same with durations. ADDP-2 does DP on DAGs in general.

Counting. The same pass can count routes. Keep ways[v], the number of cheapest routes to v. When an offer is cheaper, v takes the offer’s count; when it is equal, the counts add. That is PATH-P6.

Where DAGs appear

• Timetables. A train timetable is a DAG when each vertex is a (station, departure time) pair: every edge goes forward in time. Earliest arrival is then one pass in time order. Many journey planners work this way.
• DP tables. Every DP whose states never depend on themselves is a shortest or longest route in the DAG of its states: the grid paths of DYNP-5, the longest increasing subsequence of DYNP-6, the edit distance of DYNP-7.
• Text and speech. Splitting a sentence into words, or choosing the most likely words for a sound, are best routes through a DAG of positions (the Viterbi method).

Now try PATH-P6, Cheapest routes in a DAG.