1. **Problem Statement:** Find the shortest path from vertex $a$ to vertex $z$ in the given graph using Dijkstra's algorithm. 2. **Graph Description:** Vertices: $a,b,c,d,e,f,g,z$. Edges with weights: $a\text{-}b(1), b\text{-}c(1), c\text{-}d(1), a\text{-}e(4), b\text{-}f(7), c\text{-}g(8), d\text{-}z(20), e\text{-}f(1), f\text{-}g(1), g\text{-}z(1)$. 3. **Dijkstra's Algorithm Formula:** - Initialize distances: $dist(a)=0$, all others $\infty$. - Set $a$ as current vertex. - For each neighbor $v$ of current vertex $u$, update $dist(v) = \min(dist(v), dist(u) + weight(u,v))$. - Mark $u$ as visited. - Select unvisited vertex with smallest $dist$ as new current vertex. - Repeat until $z$ is visited. 4. **Initialization:** - $dist = \{a:0, b:\infty, c:\infty, d:\infty, e:\infty, f:\infty, g:\infty, z:\infty\}$ - Visited set = $\emptyset$ 5. **Step-by-step Table:** | Step | Current | Distances (a,b,c,d,e,f,g,z) | Visited | |-------|---------|-----------------------------|---------| | 0 | - | (0, \infty, \infty, \infty, \infty, \infty, \infty, \infty) | {} | | 1 | a | (0, 1, \infty, \infty, 4, \infty, \infty, \infty) | {a} | | 2 | b | (0, 1, 2, \infty, 4, 8, \infty, \infty) | {a,b} | | 3 | c | (0, 1, 2, 3, 4, 8, 10, \infty) | {a,b,c} | | 4 | d | (0, 1, 2, 3, 4, 8, 10, 23) | {a,b,c,d} | | 5 | e | (0, 1, 2, 3, 4, 5, 10, 23) | {a,b,c,d,e} | | 6 | f | (0, 1, 2, 3, 4, 5, 6, 23) | {a,b,c,d,e,f} | | 7 | g | (0, 1, 2, 3, 4, 5, 6, 7) | {a,b,c,d,e,f,g} | | 8 | z | (0, 1, 2, 3, 4, 5, 6, 7) | {a,b,c,d,e,f,g,z} | 6. **Explanation:** - From $a$, neighbors $b$ and $e$ get distances 1 and 4. - From $b$, neighbors $c$ and $f$ updated: $c=2$, $f=8$. - From $c$, neighbors $d$ and $g$ updated: $d=3$, $g=10$. - From $d$, neighbor $z$ updated: $z=23$. - From $e$, neighbor $f$ updated: $f=5$ (better than 8). - From $f$, neighbor $g$ updated: $g=6$ (better than 10). - From $g$, neighbor $z$ updated: $z=7$ (better than 23). 7. **Shortest path distance:** $dist(z) = 7$. 8. **Shortest path reconstruction:** - $z$ came from $g$ (distance 6 + 1 = 7) - $g$ came from $f$ (distance 5 + 1 = 6) - $f$ came from $e$ (distance 4 + 1 = 5) - $e$ came from $a$ (distance 0 + 4 = 4) So path is $a \to e \to f \to g \to z$. **Final answer:** The shortest path from $a$ to $z$ is $a \to e \to f \to g \to z$ with total distance 7.