## Dry run of Shortest Path for DAG

## Dry Run

Here is a step by step run of the algorithm:

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

- 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.
- 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.

**STEP 2: **Relax the outgoing edges of vertex b.

- Edge (b, c) : Vertex c has a cost (5). Hence the relaxation will depend on the following condition
- 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.
- else let cost of c remain unchanged.

- 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.
- 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.

- Edge (c, d) : Vertex d has a cost (5). Hence the relaxation will depend on the following condition
- 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.
- else let cost of d remain unchanged.

- Edge (c, e) : Vertex e has a cost (6). Hence the relaxation will depend on the following condition
- 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.
- else let cost of e remain unchanged.

**STEP 4: **Relax the outgoing edges of vertex d.

- Edge (d, e) : Vertex e has a cost (6). Hence the relaxation will depend on the following condition
- 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.
- else let cost of d remain unchanged.

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

Continue: Applications of Shortest Path of DAG