Topological sort and Dijkstra

Why it matters

Build systems, course prerequisites, spreadsheet recalculation and route planners all need one of two answers. The first answer is an order in which to do a list of dependent jobs, so that nothing starts before its inputs are ready. The second answer is the cheapest way to get from one place to another when each road has a cost. The first is called topological sorting, and the second is solved by Dijkstra's algorithm. Both come up often in interviews, and both are short once the idea is clear.

This lesson uses the adjacency lists from the first lesson, the queue from the BFS lesson and the heap from the heaps module. If you have not used priority_queue before, read the heaps lesson first. The rest of this lesson explains everything else.

Directed graphs with no cycles

A directed graph has one-way edges, written a -> b in this lesson. A directed acyclic graph, shortened to DAG, is a directed graph with no cycle. A cycle here means you can follow arrows and return to where you started. A DAG has no such loop, so every chain of arrows must end somewhere.

Many real things form DAGs. Think about getting dressed. You put on socks before shoes, and a shirt before a jacket. Each rule is an arrow from the first item to the second. The rules form a DAG because nobody has to put on socks after their shoes in order to put on socks before them.

A topological order is a list of all the vertices in which every arrow a -> b has a before b. For the dressing rules, one topological order is socks, shoes, shirt, jacket. Another is shirt, socks, jacket, shoes. Both respect every rule, so the order is not unique. Any valid order is an acceptable answer unless the problem asks for a specific one.

A cycle makes a topological order impossible. If a -> b and b -> a, then a would have to come before b and b before a. Topological sorting therefore doubles as a cycle detector for directed graphs. If the sort cannot finish, there is a cycle.

Kahn's algorithm

Kahn's algorithm is the most common method, and it is easy to reason about. Its key idea uses the in-degree of each vertex. The in-degree is the number of arrows pointing into a vertex, which is the number of unmet prerequisites.

A vertex with in-degree 0 has no prerequisites left. It can be done now. So the algorithm works like this:

1. Count the in-degree of every vertex.
2. Put every vertex with in-degree 0 into a queue.
3. Take a vertex out of the queue and add it to the answer.
4. For each arrow out of that vertex, subtract 1 from the in-degree of the target. If a target's in-degree becomes 0, put it in the queue.
5. Repeat until the queue is empty.

If the answer has all n vertices, you have a topological order. If fewer than n vertices were added, the leftover vertices all wait for each other, which means they are on a cycle, or wait for a vertex that is on a cycle.

Think of it like a line for a ride at a theme park, where each person in the line needs a ticket from someone else first. A person with no one to wait for steps up, and when they leave, the people who were waiting for them may now step up. If the line stops moving with people still standing in it, there is a loop of waiting. Nobody can go first, so the ride cannot start.

Here is a worked example with six vertices. The edges are 5 -> 2, 5 -> 0, 4 -> 0, 4 -> 1, 2 -> 3 and 3 -> 1. The in-degrees start as: vertex 0 has 2, vertex 1 has 2, vertex 2 has 1, vertex 3 has 1, and vertices 4 and 5 have 0. The queue starts as [4, 5].

Pop 4. Add it to the answer. Its arrows go to 0 and 1. The in-degree of 0 drops from 2 to 1, and the in-degree of 1 drops from 2 to 1. Neither is 0, so nothing is pushed. Queue [5]. Answer 4.

Pop 5. Its arrows go to 2 and 0. The in-degree of 2 drops from 1 to 0, so push 2. The in-degree of 0 drops from 1 to 0, so push 0. Queue [2, 0]. Answer 4 5.

Pop 2. Its arrow goes to 3. The in-degree of 3 drops from 1 to 0, so push 3. Queue [0, 3]. Answer 4 5 2.

Pop 0. It has no outgoing arrows. Queue [3]. Answer 4 5 2 0.

Pop 3. Its arrow goes to 1. The in-degree of 1 drops from 1 to 0, so push 1. Queue [1]. Answer 4 5 2 0 3.

Pop 1. It has no outgoing arrows. Queue empty. Answer 4 5 2 0 3 1, which has all six vertices, so the order is valid.

Step through the queue below. Watch the answer grow one vertex at a time, and notice when each vertex joins the queue.

Kahn's algorithm: the queue contents after each pop for the six-vertex example

Notice that the queue is used in FIFO order here. That is not required for correctness. Any order that takes vertices from the queue in some order gives a valid answer, because a vertex only enters the queue when everything before it is done. The first program below uses a plain queue, so the output matches the trace above exactly.

The program reads a directed graph and prints a topological order, or a message saying there is a cycle.

Type this into the Input box. The first line holds n and m, the number of vertices and arrows. The next lines are the six arrows from the trace:

6 6
5 2
5 0
4 0
4 1
2 3
3 1

The program prints:

order: 4 5 2 0 3 1

Now type a graph with a cycle, the arrows 0 -> 1, 1 -> 2 and 2 -> 1. Vertex 0 has no prerequisites, but vertices 1 and 2 wait for each other:

3 3
0 1
1 2
2 1

The program prints:

cycle: only 1 of 3 vertices can be ordered

Read the program. indeg[b]++ counts each arrow that points into b. The first loop puts the free vertices in the queue. The while loop is the algorithm, and the test --indeg[w] == 0 does two things at once: it lowers the count and checks whether the vertex is now free. In the cycle example, vertex 1 starts with in-degree 2, since both 0 and 2 point to it. Only 0 is free, so only 0 is popped. Lowering 1 from 2 to 1 is not enough, and 2 never has its count lowered, so the queue empties with two vertices unused.

Time is O(n + e). Each vertex is popped once and each arrow is looked at once. The space is O(n + e) for the lists plus O(n) for the counts and the queue.

Getting the smallest order

Sometimes many orders are valid and the problem asks for the smallest one. The usual meaning of smallest is the one that is smallest when compared number by number from the front. The rule that produces it is simple: whenever several vertices are ready, take the lowest-numbered one. The queue does not do that, because it hands out vertices in the order they became ready. A min-heap does.

Run the six-vertex example again with a min-heap in place of the queue. The ready set starts as {4, 5}, and the heap gives 4. Vertex 4 lowers the in-degrees of 0 and 1, but neither reaches 0. The ready set is {5}, so 5 comes out. It makes 2 and 0 ready. The ready set is {0, 2}, and the heap gives 0, which has no outgoing arrows. The ready set is {2}, so 2 comes out and makes 3 ready. Then 3 comes out, which makes 1 ready, and 1 comes out last.

The order is 4 5 0 2 3 1. The queue gave 4 5 2 0 3 1. The two orders agree on the first two numbers. The third number is 0 in the new order and 2 in the old one, and 0 is smaller, so the new order is the smallest. Every heap operation costs a logarithm, so the whole sort takes O((n + e) log n). That is the price of asking for the smallest answer.

The depth-first alternative

Topological order can also come from the depth-first search of the previous lesson. Run DFS on the whole graph, and record the order in which vertices finish. Then read the finish order backwards. The result is a topological order. The reason is that a vertex finishes only after everything reachable from it has finished, so every arrow from it leads to a vertex that finished earlier, and reading backwards puts it first.

A tiny example makes this clear. Take the arrows 0 -> 1, 0 -> 2 and 1 -> 2. Run DFS from 0. It enters 1, enters 2, and 2 finishes first because it has no arrows out. Then 1 finishes. Then 0 looks at its second arrow to 2, which is already finished, and then 0 finishes last. The finish order is 2, 1, 0. Reading it backwards gives 0, 1, 2, which respects all three arrows.

Kahn's algorithm reports cycles directly by counting. The DFS version reports a cycle when it sees a grey vertex, meaning one still on the current path. Either way the check is linear. In an interview, Kahn's algorithm is easier to explain, and it is the one most people write.

Dijkstra's algorithm

Now turn to weighted graphs. Each edge has a cost, and you want the cheapest total cost from a source to each other vertex. Breadth-first search cannot do this, because it counts edges, not costs. A route with two cheap edges can beat a route with one expensive edge, and BFS does not know the difference.

Dijkstra's algorithm finds the cheapest cost from one source to every vertex, as long as every edge cost is zero or more. It keeps a best-known cost for each vertex. At the start, the source has cost 0 and every other vertex has no known cost, which we write as infinity. It repeats one step. Take the vertex with the lowest best-known cost that is not finished yet. Finish it. Then look at each edge out of it, and see whether going through it makes the neighbour cheaper. If it does, update the neighbour's cost. This update is called relaxing the edge.

A min-heap makes the step fast. The heap holds pairs of (cost, vertex). Pop gives the cheapest pair in logarithmic time. Each time a cost improves, push the new pair. A pair can become out of date, because the vertex may have improved again since. The usual trick is to skip a popped pair if its cost is larger than the vertex's current best. That is the test if (d > dist[v]) continue; in the programs.

Why does it work? When a vertex has the lowest cost in the heap, no other route can beat it. Any other route to it must leave the finished vertices, and every edge cost is zero or more, so the total cannot go below the cost already seen. This is the step where the non-negative rule matters, and we return to it in the mistakes section.

The heap is the part that is easiest to lose track of, so step through the search below. It shows each pop, including the out-of-date pairs that get skipped.

Here is the example graph, with six edges that can be walked in either direction: 0-1 costs 4, 0-2 costs 1, 2-1 costs 2, 1-3 costs 1, 2-3 costs 5 and 3-4 costs 3. Start at vertex 0. The heap starts as (0, 0).

Pop (0, 0). Vertex 0 is finished with cost 0. Relax 0-1: cost 0 + 4 = 4, which is better than infinity, so set dist[1] = 4 and push (4, 1). Relax 0-2: cost 0 + 1 = 1, so set dist[2] = 1 and push (1, 2). The heap now holds (1, 2) and (4, 1).

Pop (1, 2). Vertex 2 is finished with cost 1. Relax 2-0: cost 1 + 1 = 2, which is not better than 0, so nothing happens. Relax 2-1: cost 1 + 2 = 3, which beats 4, so set dist[1] = 3 and push (3, 1). Relax 2-3: cost 1 + 5 = 6, so set dist[3] = 6 and push (6, 3). The heap now holds (3, 1), (4, 1) and (6, 3).

Pop (3, 1). Vertex 1 is finished with cost 3, which matches dist[1], so it is current. Relax 1-3: cost 3 + 1 = 4, which beats 6, so set dist[3] = 4 and push (4, 3). The other edges from 1 do not help. The heap holds (4, 1), (4, 3) and (6, 3).

Pop (4, 1). This pair is out of date, because dist[1] is 3 and the pair says 4. Skip it.

Pop (4, 3). Vertex 3 is finished with cost 4. Relax 3-4: cost 4 + 3 = 7, so set dist[4] = 7 and push (7, 4). Relax 3-2: cost 4 + 5 = 9, which is not better than 1. Relax 3-1: cost 4 + 1 = 5, which is not better than 3.

Pop (6, 3). Out of date, because dist[3] is 4. Skip it.

Pop (7, 4). Vertex 4 is finished with cost 7. It has no better routes. The heap is empty, and the costs are final: 0, 3, 1, 4, 7 for vertices 0 to 4. The next program prints these results, so you can check the trace against it.

Dijkstra relaxations on the example graph, with the final cost at each vertex

Cheapest path with the route

Costs are useful, but most people also want the route. The method is the same as the parent array from the BFS lesson. Whenever a relaxation improves dist[w] through v, record parent[w] = v. At the end, walk back from the target through the parents.

The second program does that for the example graph. It asks for a source and a target, and prints the cost and the route.

Type this into the Input box. The first line is n m s t: five vertices, six edges, source 0 and target 4. The edges follow, each with its cost:

5 6 0 4
0 1 4
0 2 1
2 1 2
1 3 1
2 3 5
3 4 3

The program prints:

cost: 7
path: 0 2 1 3 4

The route is 0, 2, 1, 3, 4, which costs 1 + 2 + 1 + 3 = 7. The direct edge 0-1 costs 4, and that is more than the route through 2, so the program does not use it. That is the whole point of Dijkstra: the cheapest route is not always the one with the fewest edges.

Two details matter. The source has no parent, so the parent array uses -1 to stop the walk. The program uses long long for the costs and LLONG_MAX for infinity, so that adding a cost to a large value does not overflow. The next section explains the overflow risk in more detail.

All distances from one source

The third program prints the cheapest cost from the source to every vertex. It uses the same main loop, but it does not need a parent array. It also prints -1 for a vertex that cannot be reached, which is the common convention in tests. The graph has six vertices, and vertex 5 is not connected to anything.

Type this into the Input box. It is the same five-vertex graph, but with six vertices, so the isolated vertex 5 is included, and the source is 0:

6 6 0
0 1 4
0 2 1
2 1 2
1 3 1
2 3 5
3 4 3

The program prints:

dist[0] = 0
dist[1] = 3
dist[2] = 1
dist[3] = 4
dist[4] = 7
dist[5] = -1

These match the trace. Vertex 1 is 3 and not 4, because the route through 2 is cheaper. Vertex 5 prints -1 because the loop never reaches it.

Look at how the output code handles INT_MAX. We do not print INT_MAX, which is a large number meaning "no route". We print -1 instead, and tests and users understand that better. Keeping the sentinel value internal and translating it at the output is a good habit.

What the heap is doing

Each finished vertex causes at most one pop that matters, and each edge can cause one push. So the heap holds at most one entry per edge that improved a cost, plus the source. Each push and pop costs O(log k), where k is the number of entries in the heap, which is never more than the number of edges. Because the total work is about one push and one pop per edge, Dijkstra with a heap runs in O((n + e) log n) time. The space is O(n + e) for the lists and the heap together.

The heap also explains the skip test. Without it, a vertex would be processed once for every stale pair in the heap, and the work could grow much larger than the number of edges. The skip test costs nothing and keeps the work in line with the edge count.

Compare this with the simpler O(n squared) version that scans all vertices for the cheapest unfinished one. On a dense graph, where the edges come close to n squared, the scan can be as fast or faster, because the heap adds a logarithm to every edge. For the sparse graphs that most problems use, the heap version is far faster, because it touches only the edges that matter.

Grids with costs

A grid where each cell has a cost is a weighted graph. The cost of a move is the cost of the cell you enter. This is the form most interview problems take, such as a robot crossing a warehouse or a path through a map with terrain costs.

The fourth program finds the least total cost from the top-left cell to the bottom-right cell. The cost of entering a cell is its digit, and the start cell is free. The priority queue now holds triples of cost, row and column, using tuple.

Type this into the Input box:

3 4
1134
1951
1111

The program prints:

min cost: 5

Check it by hand. One cheapest route goes down the left column and then along the bottom row: it enters (1,0) costing 1, (2,0) costing 1, (2,1) costing 1, (2,2) costing 1 and (2,3) costing 1. The total is 5. Routes through the top row or through the big digits cost more. The start cell (0,0) holds a 1, but its cost is not counted, which is the rule in the statement.

The changes from the earlier program are small. The cost of a move is grid[nr][nc] - '0', which turns the character '7' into the number 7. The rest of the logic is the same. This is the power of Dijkstra: the cost can come from anywhere, and the algorithm does not change.

What goes wrong with a negative edge

Dijkstra needs the non-negative rule. Here is why, with a real example. Take four vertices and four directed edges: 0 -> 1 costs 1, 0 -> 2 costs 5, 2 -> 1 costs -10 and 1 -> 3 costs 1. The true cheapest costs from 0 are: vertex 1 costs -5 (through 0, 2, 1), vertex 2 costs 5, and vertex 3 costs -4 (through 1).

Now run the textbook version, which marks a vertex finished when it is popped and never looks at a finished vertex again. The first pop is (0, 0). It sets dist[1] = 1 and dist[2] = 5. The next pop is (1, 1), which finishes vertex 1 at cost 1 and sets dist[3] = 2. Vertex 1 is now finished. Later the edge 2 -> 1 offers 5 - 10 = -5, which is better than 1, so dist[1] becomes -5. But vertex 1 is already finished, so the program does not relax its edge 1 -> 3 again. Vertex 3 stays at 2.

The output is dist[3] = 2, but the true answer is -4. The finished vertex was wrong, and nothing went back to fix the vertices after it. This is the failure the proof warned about. With a negative edge, the closest unfinished vertex can become cheaper later, so a vertex marked as final is not final.

The program below runs both variants on this graph. The variant that stops relaxing finished vertices gives the wrong answer for vertex 3. The variant that re-pushes every improvement gives the right answer here, but it is no longer the algorithm with the speed guarantee. Its work is not bounded by the edges in the worst case, so do not rely on it. When an edge can be negative, use Bellman-Ford, which the next lesson covers.

#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int main() {
    int n = 4;
    vector<vector<pair<int, int>>> adj(n);
    adj[0] = {{1, 1}, {2, 5}};
    adj[1] = {{3, 1}};
    adj[2] = {{1, -10}};
    for (int variant = 0; variant < 2; variant++) {
        vector<long long> dist(n, LLONG_MAX);
        vector<bool> done(n, false);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
        dist[0] = 0;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (d > dist[v]) continue;
            if (variant == 1 && done[v]) continue;
            done[v] = true;
            for (auto [w, c] : adj[v])
                if (d + c < dist[w]) {
                    dist[w] = d + c;
                    pq.push({dist[w], w});
                }
        }
        cout << (variant == 0 ? "lazy: " : "visited: ");
        for (int v = 0; v < n; v++) cout << dist[v] << " ";
        cout << "\n";
    }
}

The program prints this, with a trailing space after each number:

lazy: 0 -5 5 -4 
visited: 0 -5 5 2 

The second line is the wrong one. Vertex 3 shows 2 where the true answer is -4. The same output shows why the rule matters. Only the variant that re-processes a vertex whose cost improved finds -4, and that is not what Dijkstra promises.

Common mistakes

The first mistake is using a negative edge with Dijkstra. Section above shows the wrong answer. Check the costs in the input before you choose the algorithm. If any cost can be negative, use Bellman-Ford.

The second mistake is forgetting the header for INT_MAX. If you write int best = INT_MAX; without #include <climits>, g++ reports this:

main.cpp: In function ‘int main()’:
main.cpp:4:16: error: ‘INT_MAX’ was not declared in this scope
    4 |     int best = INT_MAX;
      |                ^~~~~~~
main.cpp:2:1: note: ‘INT_MAX’ is defined in header ‘<climits>’; this is probably fixable by adding ‘#include <climits>’

Add the header the note names. The programs in this lesson include it.

The third mistake is adding to infinity. If dist[v] is INT_MAX for an unreached vertex, the expression dist[v] + c overflows. For signed integers, overflow is undefined behaviour in C++, and in practice it often gives a large negative number. That negative number looks like a very short route, so the program accepts it and gives a wrong answer. Only relax from vertices that have a real distance, as the programs do with the check on d, or use a sentinel large enough that the sum still fits.

The fourth mistake is a max-heap by accident. priority_queue is a max-heap by default, so the largest pair comes out first. Dijkstra then processes the most expensive vertices first. The program may still print correct costs, because it keeps relaxing edges until nothing improves, but the running time can grow far beyond the number of edges. The fix is greater<> in the template, as in the programs. Check the template every time you write priority_queue.

The fifth mistake is assuming a topological order is unique. Two different orders can both be correct. A grader that compares exact output may reject a valid answer. Read the problem statement. If it says "print any valid order", your program can print any valid order. If it asks for the smallest order, say so and use a min-heap instead of a queue.

The sixth mistake is forgetting the skip test in Dijkstra. Without if (d > dist[v]) continue;, the program still gives correct answers, but it does extra work for each stale pair and can slow down badly on large graphs.

A debugging walkthrough

A classmate's grid program prints min cost: 2147483647 for a small grid that should give 5. That number is INT_MAX, the starting value of dist. What do you check first?

Start by finding where the number comes from. The value is the starting value of dist, so the destination was never relaxed. Check the loop that relaxes the neighbours. A common cause is a bounds test that is written wrong. For example, nr > R instead of nr >= R lets the program look one row past the grid. A cell past the grid is never reached correctly, so dist at the real destination stays at its starting value.

Next, print the pairs as they are popped. Add a cerr line inside the loop, just after pq.pop(). Use cerr for debugging because it is separate from the answer stream. Run the small grid. You should see the start (0, 0, 0), then pairs for the neighbours with costs 1 and 1, and so on. If you see no pairs after the first pop, the neighbours are being skipped. Check the bounds test and the cost calculation.

If the pairs look right but the answer is still the sentinel, check the output. The program must print dist[R - 1][C - 1], not dist[0][0] or a value with the rows and columns swapped. Swapped indexes are a classic bug in grid code, and they pass on square grids. Test with a rectangle, as in the example, to catch them.

Patterns that come up in interviews

Topological order appears in course schedules, where the question is whether all courses can be finished, and in alien dictionary problems, where letters must be ordered from sorted words. In both, count in-degrees, run Kahn's algorithm, and check whether all vertices came out. Many interview questions ask for lexicographically smallest orders, and then you replace the queue with a min-heap, as the practice exercise shows.

Dijkstra appears in network delay problems, where the answer is the time for a signal to reach every node, which is the largest of the costs. It also appears in "minimum effort" grid problems, where the cost of a path is the largest step on it, a variant that uses a different combining rule in the relaxation. Recognise a cost per move, and you have a Dijkstra problem.

When a question combines both, such as a task list with time costs, the usual approach is to run Kahn's algorithm to get the order, and then compute earliest start times in that order. That is a standard dynamic-programming pattern over a DAG.

Practice

1. Given course prerequisites as pairs a b (meaning a before b), decide whether all courses can be finished. Hint: run Kahn's algorithm and compare the count of output vertices with n.

2. Change the Kahn program so that it prints the lexicographically smallest topological order. Hint: replace the queue with a priority_queue using greater<>, so the smallest available vertex comes out first.

3. Print the cheapest route to vertex 4 in the Dijkstra path program, but treat the edges as one-way from a to b. Hint: remove the second adj[b].push_back line, and check what the output becomes.

4. Why does the test if (d > dist[v]) continue; matter for speed? Hint: count how many pops happen for a vertex that improved three times.

5. Modify the grid program so that it prints the route, not only the cost. Hint: store the parent as a pair of row and column, or store the row and column in a single number such as r * C + c.

6. A task list has n tasks and some pairs a b meaning task a must finish before task b. Each task takes a number of days. Find the earliest day each task can finish. Hint: after Kahn's order is computed, for each task in order, its finish day is its duration plus the largest finish day of its prerequisites.

7. Show that Kahn's algorithm reports a cycle when the sum of in-degrees never drops to zero for some vertex. Hint: use the cycle example from the lesson and follow which counts go down.

8. Write a Dijkstra variant that uses a plain array and no heap, scanning all vertices for the smallest unfinished one each step. Hint: the scan costs O(n) per step, so the whole run is O(n squared + e). Compare the speed on a graph with 2000 vertices.

9. The "minimum effort" grid problem asks for the path where the largest single step difference between neighbouring cells is as small as possible. Explain how you would change Dijkstra for it. Hint: change how the cost of a path is combined, from a sum to a maximum.

10. Explain in one paragraph why a DAG cannot have a cycle when Kahn's algorithm finishes with all vertices. Hint: a vertex on a cycle always keeps at least one incoming arrow from another vertex on the same cycle.

What you now know

• A topological order lists the vertices of a DAG so that every arrow goes from earlier to later. It is not unique.
• Kahn's algorithm uses in-degrees and a queue. If it outputs fewer than n vertices, the graph has a cycle.
• The DFS alternative reads finish times backwards to get a topological order.
• Dijkstra finds the cheapest cost from one source, using a min-heap and the rule of relaxing edges.
• Skip a popped pair whose cost is out of date. It keeps the work tied to the number of edges.
• Dijkstra needs every edge cost to be zero or more. With a negative edge, a finished vertex can become cheaper later, and the answer is wrong.
• Grid costs and route tracing use the same method with small changes.
• Dijkstra runs in O((n + e) log n) time with a heap.