Skip to main content

Dijkstra shortest path (2069 Bhadra)

Short answer

Dijkstra's algorithm iteratively fixes the vertex with smallest tentative distance, updating neighbors. The shortest distance from a to z is 10, via paths like a-b-e-z (4+4+2) or a-c-e-z (5+3+2).

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 5, b-d 3, b-e 4, d-e 1, d-z 4, c-e 3, e-z 2]

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 5, b–d 3, b–e 4, d–e 1, d–z 4, c–e 3, e–z 2.

Trace

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

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

Result

Shortest distance from a to z = 10.

There are 3 shortest paths of the same length 10 (highlight all of them):

  • a → b → d → e → z
  • a → b → e → z
  • a → c → e → z

Answer: shortest path length = 10. (Edges a–b–e–z: 4 + 4 + 2; a–c–e–z: 5 + 3 + 2; a–b–d–e–z: 4 + 3 + 1 + 2.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →