Skip to main content

Dijkstra shortest path (2073 Magh)

Short answer

Using Dijkstra's algorithm, the shortest path from a to Z is a–c–e–Z with total length 3.

Find the shortest path from vertex a to vertex Z. Highlight the shortest paths in the graph. [Figure: weighted graph on vertices a, b, c, d, e, Z with edges a-b 4, a-c 1, a-d 4, b-c 3, b-Z 3, c-d 2, c-e 1 [?], d-e 2, e-Z 1 [exact placement of some weights unclear in scan]]

Dijkstra's algorithm (non-negative weights) labels every vertex with the best distance known so far and fixes one vertex at a time:

  1. Give the source distance 0 and every other vertex ∞. All vertices are temporary.
  2. Make the temporary vertex with the smallest label permanent.
  3. For each temporary neighbour v of the new permanent vertex u: if d(u) + w(u,v) < d(v), set d(v) = d(u) + w(u,v) and record u as predecessor.
  4. Repeat steps 2 and 3 until the target (or all vertices) is permanent.

Graph as read

Reading: the weight of edge c–e is taken as 1 (marked unclear in the scan); the other weights are as listed. Source a, target Z.

Edges: a–b 4, a–c 1, a–d 4, b–c 3, b–Z 3, c–d 2, c–e 1, d–e 2, e–Z 1.

Trace

Each cell shows label = distance(predecessor). Bold marks the vertex made permanent in that step; ✓ means already permanent.

StepFixedabcdeZ
1a04(a)1(a)4(a)∞∞
2c✓4(a)1(a)3(c)2(c)∞
3e✓4(a)✓3(c)2(c)3(e)
4d✓4(a)✓3(c)✓3(e)
5Z✓4(a)✓✓✓3(e)
6b✓4(a)✓✓✓✓

Result

Shortest distance from a to Z = 3.

Shortest path (highlight these edges): a → c → e → Z with edge weights 1 + 1 + 1 = 3.

Answer: shortest path a to Z = a → c → e → Z, length 1 + 1 + 1 = 3. Other routes are longer (a–c–d–e–Z = 6, a–b–Z = 7).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →