StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q55SE

Expert-verifiedFound in: Page 738

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

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.

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.

94% of StudySmarter users get better grades.

Sign up for free