Question

Find the shortest path between the vertices\({\bf{a}}\)and\({\bf{z}}\)that passes through the vertex f in the weighted graph in Exercise 3 in Section 10.6.

Short answer

The shortest path is\(\left( {acdfgz} \right) = 17\;unit\).

Step-by-step solution

We the graph as

Step 2: Find the shortest path between the vertices \({\bf{a}}\) and \({\bf{z}}\)

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[ {c\left( {a,3} \right)} \right],\left( {a,4} \right)\]	to\(c:\left( {ac} \right)\)of length 3
\[c\left( {a,3} \right)\]	\[d\left( {c,3 + 3} \right),\left[ {b\left( {a,4} \right)} \right],e\left( {c,3 + 6} \right)\]	to\(b:\left( {ab} \right)\)of length 4
\[b\left( {a,4} \right)\]	\[\left[ {d\left( {c,6} \right)} \right],\]	to\(d:\left( {acd} \right)\)of length 6
\[d\left( {c,6} \right)\]	\[\left[ {e\left( {d,7} \right)} \right],f\left( {d,11} \right)\]	to\(e:\left( {acde} \right)\)of length 7
\[e\left( {d,7} \right)\]	\[\left[ {g\left( {e,12} \right)} \right]\]	to\(g:\left( {ac\deg } \right)\)of length 12
\[g\left( {e,12} \right)\]	\[\left[ {f\left( {d,11} \right)} \right]\]	to\(f:\left( {acdf} \right)\)of length 11
\[f\left( {d,11} \right)\]	\[\left[ {g\left( {f,13} \right)} \right],z\left( {f,18} \right)\]	to\(g:\left( {acdfg} \right)\)of length 13
\[g\left( {f,13} \right)\]	\[\left[ {z\left( {f,13} \right)} \right]\]	to\(z:\left( {acdgz} \right)\)of length 17

Hence, finally we have obtained shortest path.