DAG Shortest Path

DAG shortest path finds shortest paths in a directed acyclic graph by processing vertices in topological order.

It works even with negative edge weights because the graph has no directed cycles.

Core Idea

In a DAG, topological order ensures that all paths into a vertex are considered before that vertex is used to update later vertices.

The algorithm initializes distances, processes vertices in topological order, and relaxes outgoing edges.

Function Contract

dag_shortest_path(graph, order, start) expects a directed acyclic weighted graph, a valid topological order of its vertices, and a start vertex.

It returns a distance dictionary. Unreachable vertices remain float("inf"). The function assumes every vertex appears as a key in graph.

Python Example

def dag_shortest_path(graph, order, start):
    distance = {node: float("inf") for node in graph}
    distance[start] = 0
 
    for node in order:
        if distance[node] == float("inf"):
            continue
 
        for neighbor, weight in graph[node]:
            distance[neighbor] = min(
                distance[neighbor],
                distance[node] + weight,
            )
 
    return distance

order must be a valid topological order.

This version assumes every vertex appears as a key in graph, even if it has no outgoing edges.

Why Topological Order Helps

In a DAG, every directed edge goes forward in some topological order. When a vertex is processed, every possible predecessor has already had a chance to improve its distance.

That means the algorithm does not need a priority queue or repeated passes over all edges.

Step-by-Step Shape

For a graph:

A -> B -> D
A -> C -> D

a valid topological order is A, B, C, D. The distance to D is computed only after B and C have both had a chance to relax their outgoing edges.

Complexity

After topological order is available, relaxing all edges is O(V + E). Computing the topological order is also O(V + E), so the whole approach is linear in the graph size.

Common Confusions

This algorithm requires a directed acyclic graph. If the graph has a directed cycle, topological order does not exist.

It is not the same as Dijkstra. The correctness comes from acyclic order, not from always choosing the currently closest vertex.

Negative weights are allowed in a DAG shortest path because cycles are impossible. A negative cycle cannot exist in an acyclic graph.

When To Use It

Use DAG shortest path when dependencies or one-way transitions form an acyclic graph and shortest path values should flow through that order.

Do not use it on an arbitrary directed graph unless acyclicity is guaranteed or checked.

The Main Point

DAG shortest path works because topological order makes every predecessor finish before a vertex is used to relax later edges.