| Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref> | | Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find [[shortest path]]s and [[longest path problem|longest paths]] from a given starting vertex in DAGs in linear time by [[Topological sorting#Application to shortest path finding|processing the vertices in a topological order]], and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges.<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref> In contrast, for arbitrary graphs the shortest path may require slower algorithms such as [[Dijkstra's algorithm]] or the [[Bellman–Ford algorithm]],<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref> and longest paths in arbitrary graphs are [[NP-hard]] to find.<ref>Cormen et al. 2001, p. 966.</ref> |
| + | Some algorithms become simpler when used on DAGs instead of general graphs, based on the principle of topological ordering. For example, it is possible to find shortest paths and longest paths from a given starting vertex in DAGs in linear time by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges. In contrast, for arbitrary graphs the shortest path may require slower algorithms such as Dijkstra's algorithm or the Bellman–Ford algorithm, and longest paths in arbitrary graphs are NP-hard to find. |