The idea: relax every edge once, in topological order

A shortest-path algorithm keeps a number dist[v] for every vertex: the length of the best path from the source found so far. It starts at 0 for the source and ∞ for everything else. To relax an edge u→v with weight w means: if dist[u] + w is smaller than dist[v], lower dist[v] and remember the edge as v's parent pointer. Every shortest-path algorithm is a choice of which edges to relax, in which order.

In a DAG (directed acyclic graph) there is a perfect order. Line the vertices up in a topological order, so every edge points forward, and take them left to right. When a vertex is taken, every edge into it has already been relaxed, so its dist is final. Relax its out-edges and move on. Each edge is checked exactly once.

The sample graph laid out in topological order S A B C D T, every edge pointing right; under each vertex its final dist: S 0, A 4, B 1, C 0, D 3, T 5; the shortest path S A C D T is green and uses the edge A to C of weight minus 4
In topological order every edge points forward: one sweep from left to right relaxes each edge once.

The algorithm

order = topological order of the graph      (Kahn's algorithm or DFS)
dist[s] = 0, dist[v] = ∞ for every other v
for u in order:
    for each edge u→v with weight w:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u

On the sample graph the order is S A B C D T. A is taken with dist = 4 and relaxes A→C = −4, so C drops from 3 to 0. C is then taken, and D and T are built on the right value: dist[T] = 5 along S → A → C → D → T, in 8 edge checks for 8 edges (Demo: DAG pass with a negative edge). The topological order comes from Kahn's algorithm or from depth-first search.

Why negative weights are fine

The proof does not look at the weights at all. Every path into v ends with an edge u→v, and u comes before v in the order. By the time v is taken, u was taken earlier with its final value and relaxed u→v. So dist[v] already holds the best of all ways in. That holds whether w is 5 or −4.

Dijkstra and Bellman-Ford on the same graph

Dijkstra's algorithm uses a different order: always the closest unsettled vertex, and a settled vertex is never changed. That is right when no edge is negative, because a longer path can only get longer. Here it settles C at 3 (via B) before it settles A at 4. When A finally relaxes A→C, it finds 0, but C is already settled. D and T were built on the wrong 3, and Dijkstra answers dist[T] = 8 (Demo: Dijkstra on the same graph).

Two rows. Dijkstra settles S 0, B 1, C 3, then A 4; the edge A to C would give 0 but C is already settled, so T ends at 8, wrong. The DAG pass takes S, A, B, C: A relaxes A to C before C is taken, C is 0 and T ends at 5, correct
Dijkstra settles C before the negative edge into it is seen; the topological order cannot make that mistake.

Bellman-Ford needs no order: it relaxes every edge in a fixed list, pass after pass, until a pass changes nothing. It is always right, but it pays for not knowing the order. With the edge list in the worst order (reverse topological) each pass moves the correct values only one edge further, so it takes 4 passes that change something and 1 clean pass: 40 edge checks instead of 8 (Demo: Bellman-Ford, 5 passes). See Dijkstra vs Bellman-Ford for the two side by side.

AlgorithmGraphsNegative edgesTimeSample graph
DAG passDAGs onlyyesO(V + E)8 checks, T = 5 ✓
DijkstraanynoO((V + E) log V)8 checks, T = 8 ✗
Bellman-Fordanyyes, finds negative cyclesO(V · E)40 checks, T = 5 ✓

Longest paths: the critical path of a project

A project is a DAG: milestones are vertices, each task is an edge from the milestone it waits for to the milestone it finishes, weighted by its duration. The earliest the project can end is the longest path from start to finish, the critical path: a delay on any of its tasks delays the end, while the other tasks have slack. Negate every duration and the longest path becomes the shortest one. All weights are now negative, which rules out Dijkstra, but the DAG pass does not care: dist[F] = −11, so the project takes 11 days, along S → B → D → F (2 + 4 + 5) (Demo: critical path). Dijkstra settles F at −10 before it reaches B's tasks and answers 10 days. Longest path in a DAG shows the same pass as dynamic programming, with max instead of min.

When the graph has a cycle

A cycle has no topological order: each vertex on it would have to come after itself. Kahn's algorithm shows this by getting stuck. In the third graph it takes S, and then A, B and C all still have an edge coming in from the cycle A → B → C → A (Demo: a cycle). Then the DAG pass cannot run and Bellman-Ford is the tool. Here the cycle's total weight is 1 + 2 − 1 = 2, not negative, so shortest paths exist and Bellman-Ford finds dist[T] = 4 in 2 passes (Demo: the cycle with Bellman-Ford). A DAG can never have a negative cycle, which is another reason the one-pass method is safe.

Cost

The topological sort is O(V + E) and the pass is O(V + E): every vertex is taken once and every edge relaxed once. No heap is needed. That makes it the fastest single-source shortest-path algorithm there is for DAGs, and the reason scheduling tools, build systems and the DP tables of dynamic programming all use it.

For shortest paths on a real graph, with negative edges and a comparison with Dijkstra, see shortest paths in a DAG.

What the page leaves out

The topological sort step by step (see the topological sort pages); the slack of each task and the latest start times in project scheduling (a second pass in reverse order); Bellman-Ford's negative cycle check after V − 1 passes; Dijkstra with a decrease-key heap; all-pairs shortest paths (Floyd-Warshall vs Johnson); and counting shortest paths.