Visualizer CodeViz · Algorithms, visualized

Part II · Shortest paths · week 4

Shortest paths in a DAG

In an acyclic digraph, relax vertices in topological order and one pass is enough. Linear time, no priority queue, and negative weights are welcome.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V + E) — linear
requiresno directed cycle
negative weightsfine
also giveslongest paths (negate)

Reference: Sedgewick & Wayne, §4.4.

Shortest paths in a DAG in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class AcyclicSP:
    # Relax vertices in topological order. When you reach v, every edge
    # that could possibly improve dist_to[v] has already been relaxed,
    # so dist_to[v] is final -- no priority queue needed, and NEGATIVE
    # weights are no problem at all.

    def __init__(self, digraph, s):
        self.dist_to = [float('inf')] * digraph.V
        self.edge_to = [None] * digraph.V
        self.dist_to[s] = 0.0
        for v in Topological(digraph).order:
            for w, weight in digraph.adj(v):
                if self.dist_to[w] > self.dist_to[v] + weight:
                    self.dist_to[w] = self.dist_to[v] + weight
                    self.edge_to[w] = v

Why it works

Why one pass suffices

Topological order guarantees every edge points forwards. So by the time the loop reaches v, every edge u→v has already been relaxed — there is no route left that could improve dist_to[v]. Each edge is relaxed exactly once and the whole computation is linear, beating Dijkstra's O(E log V) with no data structure more advanced than a list.

The general lesson: if you can find an order in which subproblems are already solved, you do not need a priority queue. That is the same insight as dynamic programming.

Negative weights are fine here

The correctness argument never mentions the sign of the weights — only the order. So this algorithm handles negative edges that would silently break Dijkstra. And since a DAG has no cycles, there can be no negative cycle to make “shortest” meaningless.

Longest paths for free

Negate every weight (or flip the comparison) and the same pass computes longest paths — which is the critical path method for scheduling: the longest path through a task DAG is the earliest possible finish time, and it tells you which tasks are on the critical path. Longest paths in a general digraph are NP-hard; in a DAG they are linear. The acyclicity is doing enormous work.

Also used for

Seam carving (a pixel DAG), content-aware resizing, parallel job scheduling with precedence constraints, and DP on DAGs generally — including the shortest-path formulation of many dynamic-programming problems.

What to try in the animation

The default is tinyEWDAG.txt from the course. Try a negative weight — Dijkstra would get it wrong, this will not.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Shortest paths in a DAG in the player →

The rest of Shortest paths