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.

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.

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.

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.