Topological Sorting

Note

Objectives

1. Apply the DFS algorithm to create a topological sorted order of vertices.
2. Explain the benefit of using the topological sorting DAG shortest paths algorithm.

Code: Topological.java

Dijkstra's algorithm is the most well-known algorithm for finding a shortest paths tree in a weighted graph, but it's not the only algorithm. There are several others that address various shortcomings of Dijkstra's algorithm, including the topological sorting DAG shortest paths algorithm. There's unfortunately no commonly-accepted shorter name for it.

A topological sorting of a directed acyclic graph (DAG) orders all the vertices in a certain way as to ensure all prerequisites for a vertex $v$ are examined before examining vertex $v$. The goal of this algorithm is to address the issue with finding shortest paths in a DAG with hidden, negative-weight shortcuts. Watch the following video through the 6:33 mark.

To find a topological sort, we can start by finding a DFS postorder: whereas a preorder traversal prints a vertex $v$ before the recursive calls, a postorder traversal prints a vertex $v$ after the recursive calls. Then, we need to reverse the DFS postorder: reverse the list we just found!

Important

Review the Topological Sort Demo and notice how the first value in the DFS postorder is 4 because 4 has no outgoing neighbors! We then add 1 after visiting all of 1's neighbors. And repeat.

Why does this work? In (forward) DFS postorder, we add the following vertices:

• The first vertex added to the result list is like a leaf in a tree: it has no outgoing neighbors so it is not a "prerequisite" for any other vertex.
• The second vertex added to the result list points to the first vertex.
• ...
• The final vertex added to the result list is the start vertex.

So the reverse DFS postorder has the first vertex (the "leaf") at the end of the result list where it belongs in the topological sorting.

Tip

Once we have a topological sorting of a DAG, building a shortest paths algorithm from it just requires looping over the vertices in the topological order and relaxing all its neighboring edges like we saw in Dijkstra's algorithm. Whereas Dijkstra's algorithm relies on a priority queue to determine which vertex to consider next, this shortest paths algorithm uses the topological sorting to determine which vertex to consider next.