DAG Shortest paths If the graph is a directed acyclic graph(DAg), we first topologically sort the vertices Determine f:V→{1,2,…, )such that(u2)∈E →f(l)<f(v) O(+ E) time using depth-first search 4 S(2 Walk through the vertices u e v in this order, relaxing the edges in Adjlu, thereby obtaining the shortest paths from s in a total of o(v+ E)time c 2001 by Charles E Leiserson Introduction to Algorithms Day31L18.16© 2001 by Charles E. Leiserson Introduction to Algorithms Day 31 L18.16 DAG shortest paths If the graph is a directed acyclic graph (DAG), we first topologically sort the vertices. Walk through the vertices u ∈ V in this order, relaxing the edges in Adj[u], thereby obtaining the shortest paths from s in a total of O(V + E) time. • Determine f : V → {1, 2, …, |V|} such that (u, v) ∈ E ⇒ f(u) < f(v). • O(V + E) time using depth-first search. 33 55 66 44 s 22 77 99 1 88 1