In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a Directed graph [Directed graph] with no directed cycles. That is, it consists of vertices [Vertices] and edges [Edges] (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered [Topological order], by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology (evolution, family trees, epidemiology) to information science (citation networks) to computation (scheduling).
Shortest path algorithm
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 (a) and longest paths (a) from a given starting vertex in DAGs in linear time by processing the vertices in a topological order (a), 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 [Dijkstra’s algorithm] or the Bellman–Ford algorithm (a), and longest paths in arbitrary graphs are NP-hard (a) to find.