Single Source Shortest Path – Directed Acyclic Graph

Dry run of Shortest Path for DAG

Dry Run

Here is a step by step run of the algorithm:

Shortest Path - Directed Acyclic Graph

STEP 1: Relax the outgoing edges of source (vertex a).

  1. Edge (a, b) : Vertex b has a cost (positive infinity). Hence the relaxation will assign a cost equal to the sum of cost at vertex (a) and the weight of the edge. cost(b) = 0 + 3 = 3.
  2. Edge (a, c) : Vertex c has a cost (positive infinity). Hence the relaxation will assign a cost equal to the sum of cost at vertex (a) and the weight of the edge. cost(c) = 0 + 5 = 5.

Shortest Path - Directed Acyclic Graph

STEP 2: Relax the outgoing edges of vertex b.

  1. Edge (b, c) : Vertex c has a cost (5). Hence the relaxation will depend on the following condition
    1. if cost of c i.e. 5 is greater that the sum of cost of b and edge weight (b, c) , then assign the new value. Here new value is 3+8 = 11.
    2. else let cost of c remain unchanged.
  2. Edge (b, d) : Vertex d has a cost (positive infinity). Hence the relaxation will assign a cost equal to the sum of cost at vertex (b) and the weight of the edge. cost(d) = 3 + 2 = 5.
  3. Edge (b, e) : Vertex e has a cost (positive infinity). Hence the relaxation will assign a cost equal to the sum of cost at vertex (b) and the weight of the edge. cost(e) = 3 + 3 = 6.

STEP 3: Relax the outgoing edges of vertex c.

  1. Edge (c, d) : Vertex d has a cost (5). Hence the relaxation will depend on the following condition
    1. if cost of d i.e. 5 is greater that the sum of cost of c and edge weight (c, d) , then assign the new value. Here new value is 5 – 2 = 3.
    2. else let cost of d remain unchanged.
  2. Edge (c, e) : Vertex e has a cost (6). Hence the relaxation will depend on the following condition
    1. if cost of e i.e. 6 is greater that the sum of cost of c and edge weight (c, e) , then assign the new value. Here new value is 5 + 3 = 8.
    2. else let cost of e remain unchanged.

 

Shortest Path - Directed Acyclic Graph

STEP 4: Relax the outgoing edges of vertex d.

  1. Edge (d, e) : Vertex e has a cost (6). Hence the relaxation will depend on the following condition
    1. if cost of e i.e. 6 is greater that the sum of cost of d and edge weight (d, e) , then assign the new value. Here new value is 3 – 4 = -1.
    2. else let cost of d remain unchanged.

STEP 5: There is no edge to relax as e is the sink vertex.