## Directed Acyclic Graph (DAG)

DAG, here directed means that each edge has an arrow denoting that the edge can be traversed in only that particular direction. Acyclic means that the graph has no cycles, i.e., starting at one node, you can never end up at the same node. DAG can be used to ﬁnd shortest path from a given source node to all other nodes. To find shortest path by using DAG, ﬁrst of all sort the vertices of graph topologically and then relax the vertices in topological order.#### Example:

Step 1: Sort the vertices of graph topologically

Step 2: Relax from S

Step 3: Relax from C

Step 4: Relax from A

Step5: Relax from B

Step6: Relax from D

### Algorithm

DagSP(G,w,s) { Topologically Sort the vertices of G for each vertex v belongs to V do d[v] = ? d[s] = 0 for each vertex u, taken in topologically sorted order do for each vertex v adjacent to u do if d[v] > d[u] + w(u,v) then d[v] = d[u] + w(u,v) }

## 0 Comments

Subscribe Us and Thanks for visiting blog.