• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q55SE

Expert-verified Found in: Page 738 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Find the second shortest path between the vertices $${\bf{a}}$$ and $${\bf{z}}$$ in Figure 3 of Section 10.6.

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

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

## Step 3: 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. ### Want to see more solutions like these? 