# Topological Sorting **A method of sorting the vertices of a [[Graph#Directed graph|directed graph]] which forms a [[Total Order Relation|linear order]] such that a vertex always appears before all vertices it considers neighbours.** ![[TopologicalSorting.svg]] *A directed graph and a topological ordering of its vertices; not all graphs have multiple topological orderings* A *topological sort* of a directed graph is a *linear ordering* of its vertices such that for all directed edges $(v, w)$, $v$ appears before $w$. A topological sort does not necessarily exist for any directed graph, only for those with no [[Cycle|cycles]], that is, a [[directed acyclic graph]]. A directed acyclic graph with a [[Hamiltonian path]] will have exactly one unique topological sort order and has the property that all *adjacent vertices* in the order are *connected* by an edge. Otherwise, the directed acyclic graph will have at least two topological sort orders. ## Algorithms Typical algorithms for the topological sorting of a directed acyclic graph have a [[Time Complexity|worst-case running time]] linear in the number of nodes and edges, that is, $O(V+E)$. - [[Depth-First Search#Topological sorting|Depth-first search]] - [[Kahn's algorithm]] ## Applications ### Dynamic programming In [[dynamic programming]], problems are divided into *overlapping subproblems* such that the results of *previous* subproblems can be used to solved future ones. The required *order of computation* for dynamic programming algorithms solving directed graph problems can be given by a *topological sorting* of the graph. #### Shortest path problem The [[shortest path problem]] for weighted [[Directed Acyclic Graph|directed acyclic graphs]] can be solved by first sorting the vertices in topological order. In the following, `s` is the source vertex. > [!Algorithm] > 1. Maintain an array `d` of the shortest path distances from `s`. Initialise `d[s]` to $0$ and `d[u]` to $\infty$ for all other vertices `u`. > 2. Additionally, maintain an array `pred` initialised to `NULL` containing the predecessor vertices of all vertices `u` along the shortest path from `s` to `u` > 3. For all vertices `u` after `s` in topological order, > 1. For all neighbours `v` of `u`, > - If `d[v] > d[u] + w`, where `w` is the weight of the edge `e(u, v)`, > 1. `d[v] = d[u] + w` > 2. `p[v] = u` As topological sorting can be achieved in $O(V+E)$, and every edge of the graph is subsequently only considered once, the time complexity remains linear in the number of nodes and edges.