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 find shortest path from a given source node to all other nodes. To find shortest path by using DAG, first of all sort the vertices of graph topologically and then relax the vertices in topological order.



Example:

Directed Acyclie Graph (DAG) | DAA

Step 1: Sort the vertices of graph topologically
Directed Acyclie Graph (DAG) | DAA

Step 2: Relax from S
Directed Acyclie Graph (DAG) | DAA

Step 3: Relax from C
Directed Acyclie Graph (DAG) | DAA

Step 4: Relax from A
Directed Acyclie Graph (DAG) | DAA

Step5: Relax from B
Directed Acyclie Graph (DAG) | DAA

Step6: Relax from D
Directed Acyclie Graph (DAG) | DAA


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)
}

Analysis:

In tlle above algorithm, the topological sort can be done in O(V+E) time (Since this is similar to DPS! see book.).The first for loop block lakes O(V) time. In case of second for loop it executes in O(V2) Time so the total running time is O(V2). Aggregate analysis gives us the running time O(E+V).


Share To:

Arogya Thapa Magar

Post A Comment:

0 comments so far,add yours