Editing Topological sorting (section)

==Application to shortest path finding==
The topological ordering can also be used to quickly compute [[shortest path problem|shortest paths]] through a [[Weighted graph|weighted]] directed acyclic graph. Let {{mvar|V}} be the list of vertices in such a graph, in topological order. Then the following algorithm computes the shortest path from some source vertex {{mvar|s}} to all other vertices:{{r|CLRS}}

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Let {{mvar|d}} be an array of the same length as {{mvar|V}}; this will hold the shortest-path distances from {{mvar|s}}. Set {{math|1=''d''[''s''] = 0}}, all other {{math|1=''d''[''u''] = ∞}}.
* Let {{mvar|p}} be an array of the same length as {{mvar|V}}, with all elements initialized to {{mono|nil}}. Each {{math|''p''[''u'']}} will hold the predecessor of {{math|''u''}} in the shortest path from {{mvar|s}} to {{mvar|u}}.
* Loop over the vertices {{mvar|u}} as ordered in {{mvar|V}}, starting from {{mvar|s}}:
** For each vertex {{mvar|v}} directly following {{mvar|u}} (i.e., there exists an edge from {{mvar|u}} to {{mvar|v}}):
*** Let {{mvar|w}} be the weight of the edge from {{mvar|u}} to {{mvar|v}}.
*** Relax the edge: if {{math|''d''[''v''] > ''d''[''u''] + ''w''}}, set
**** {{math|''d''[''v''] ← ''d''[''u''] + ''w''}},
**** {{math|''p''[''v''] ← ''u''}}.
{{frame-footer}}
</div>

Equivalently:
<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Let {{mvar|d}} be an array of the same length as {{mvar|V}}; this will hold the shortest-path distances from {{mvar|s}}. Set {{math|1=''d''[''s''] = 0}}, all other {{math|1=''d''[''u''] = ∞}}.
* Let {{mvar|p}} be an array of the same length as {{mvar|V}}, with all elements initialized to {{mono|nil}}. Each {{math|''p''[''u'']}} will hold the predecessor of {{mvar|u}} in the shortest path from {{mvar|s}} to {{mvar|u}}.
* Loop over the vertices {{mvar|u}} as ordered in {{mvar|V}}, starting from {{mvar|s}}:
** For each vertex {{mvar|v}} into {{mvar|u}} (i.e., there exists an edge from {{mvar|v}} to {{mvar|u}}):
*** Let {{mvar|w}} be the weight of the edge from {{mvar|v}} to {{mvar|u}}.
*** Relax the edge: if {{math|''d''[''u''] > ''d''[''v''] + ''w''}}, set
**** {{math|''d''[''u''] ← ''d''[''v''] + ''w''}},
**** {{math|''p''[''u''] ← ''v''}}.
{{frame-footer}}
</div>

On a graph of {{mvar|n}} vertices and {{mvar|m}} edges, this algorithm takes {{math|Θ(''n'' + ''m'')}}, i.e., [[Linear time|linear]], time.{{r|CLRS}}