algorithm computes the shortest path from some source vertex to all other vertices: Let be an array of the same length as ; this will hold the shortest-path distances from . Set , all other . Let be an array of the same length as , with all elements initialized to . Each will hold the predecessor of in the shortest path from to . Loop over the vertices as ordered in , starting from : For each vertex directly following (i.e., there exists an edge from to ): Let be the weight of the edge from to . Relax the edge: if , set , . Equivalently: Let be an array of the same length as ; this will hold the shortest-path distances from . Set , all other . Let be an array of the same length as , with all elements initialized to . Each will hold the predecessor of in the shortest path from to . Loop over the vertices as ordered in , starting from : For each vertex into (i.e., there exists an edge from to ): Let be the weight of the edge from to . Relax the edge: if , set , . On a graph of vertices and edges, this algorithm takes , i.e., linear, time. Uniqueness If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other. Therefore, it is possible to test in linear time whether a unique ordering exists, and whether a Hamiltonian path exists, despite the NP-hardness of the Hamiltonian path problem for more general directed graphs (i.e. cyclic directed graphs). Relation to partial orders Topological orderings are also closely related to the concept of a linear extension of a partial order in mathematics. A partially ordered set is just a set of objects together with a definition of the "≤" inequality relation, satisfying the axioms