1. **Problem Statement:** Find the length of the shortest path from vertex $a$ to vertex $z$ in the given weighted graph using Dijkstra's algorithm. 2. **Dijkstra's Algorithm Overview:** - It finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative weights. - The algorithm maintains a set of vertices with known shortest distances and updates distances to neighboring vertices. 3. **Initialization:** - Set distance to $a$ as 0: $d(a) = 0$. - Set distances to all other vertices as infinity: $d(b) = d(c) = d(d) = d(e) = d(f) = d(g) = d(z) = \infty$. - Mark all vertices as unvisited. 4. **Step-by-step Execution:** - Start at $a$ (distance 0). - Update neighbors of $a$: - $d(b) = \min(\infty, 0 + 4) = 4$ - $d(c) = \min(\infty, 0 + 3) = 3$ - Mark $a$ visited. - Next, pick unvisited vertex with smallest distance: $c$ ($d(c) = 3$). - Update neighbors of $c$: - $d(b) = \min(4, 3 + 2) = 4$ (no change) - $d(d) = \min(\infty, 3 + 6) = 9$ - Mark $c$ visited. - Next, pick $b$ ($d(b) = 4$). - Update neighbors of $b$: - $d(d) = \min(9, 4 + 5) = 9$ (no change) - $d(c)$ already visited. - Mark $b$ visited. - Next, pick $d$ ($d(d) = 9$). - Update neighbors of $d$: - $d(f) = \min(\infty, 9 + 5) = 14$ - $d(g) = \min(\infty, 9 + 1) = 10$ - Mark $d$ visited. - Next, pick $g$ ($d(g) = 10$). - Update neighbors of $g$: - $d(z) = \min(\infty, 10 + 3) = 13$ - Mark $g$ visited. - Next, pick $z$ ($d(z) = 13$). - Mark $z$ visited. - Next, pick $f$ ($d(f) = 14$). - Update neighbors of $f$: - $d(g)$ already visited. - $d(z) = \min(13, 14 + 7) = 13$ (no change) - Mark $f$ visited. 5. **Result:** The shortest distance from $a$ to $z$ is $d(z) = 13$. **Final answer:** The length of the shortest path from $a$ to $z$ is **13**.