Question

Find the second shortest path between the vertices\({\bf{a}}\)and\({\bf{z}}\)in Figure 3 of Section 10.6.

Short answer

The second shortest path is \(\left( {abez} \right) = 8\,unit\).

Step-by-step solution

Step 1:The graph is given below

Step 2:Find the second shortest path between the vertices

Applying Dijkstra’s algorithm

1- Label the start vertex as zero. In the present case\(a\left( { - ,0} \right)\).

2- Box this number as permanent (permanent label).

3-Label each vertex that is connected to the start vertex with its distance.

4-Box are the smallest number as (permanent label as shown in the table below within the square bracket).

5-From this vertex, consider the distance to each connected or neighbouring vertex.

6-Find he vertex with smallest distance and make it permanent.

7-Repeat the step 4 until the destination vertex is boxed.

The table is given below

Tree vertices	Neighbouring vertices	Shortest from a
\(a\left( { - ,0} \right)\)	\(\left( {d\left( {a,2} \right)} \right),b\left( {a,4} \right)\)	to\(d:\left( {ad} \right)\)of length 2
\(d\left( {a,2} \right)\)	\(\left( {b\left( {a,4} \right)} \right),e\left( {d,2 + 3} \right)\)	to\(b:\left( {ab} \right)\)of length 4
\(b\left( {a,4} \right)\)	\(\left( {e\left( {b,4 + 3} \right)} \right),c\left( {b,4 + 3} \right)\)	to\(e:\left( {abe} \right)\)of length 7
\(e\left( {b,7} \right)\)	\(\left( {z\left( {e,7 + 1} \right)} \right)\)	to \(z:\left( {abez} \right)\)of length 8

Hence, finally we have obtained second shortest path.