Skip to main content

Dijkstra shortest path (2068 Bhadra)

Short answer

Dijkstra's algorithm iteratively fixes the vertex with smallest tentative distance, updating neighbors. The shortest path length from a to z is 13, along a-c-b-d-e-z (2+1+5+2+3).

Use Dijkstra's algorithm to find the length of the shortest path between the vertices a and z in the weighted graph displayed below. [Figure: weighted graph on vertices a, b, c, d, e, z with edges a-b 4, a-c 2, b-c 1, b-d 5, c-d 8, c-e 10, d-e 2, d-z 6, e-z 3]

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

Source a, target z.

Edges: a–b 4, a–c 2, b–c 1, b–d 5, c–d 8, c–e 10, d–e 2, d–z 6, e–z 3.

Trace

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

StepFixedabcdez
1a04(a)2(a)∞∞∞
2c✓3(c)2(a)10(c)12(c)∞
3b✓3(c)✓8(b)12(c)∞
4d✓✓✓8(b)10(d)14(d)
5e✓✓✓✓10(d)13(e)
6z✓✓✓✓✓13(e)

Result

Shortest distance from a to z = 13.

Shortest path (highlight these edges): a → c → b → d → e → z with edge weights 2 + 1 + 5 + 2 + 3 = 13.

Answer: shortest path length = 13 along a → c → b → d → e → z (2 + 1 + 5 + 2 + 3).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →