Skip to main content

Dijkstra shortest path (2071 Bhadra)

Short answer

The shortest path from a to z has length 10, following a–b–c–e–z.

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

Trace

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

StepFixedabcdez
1a01(a)4(a)∞∞∞
2b✓1(a)3(b)10(b)∞∞
3c✓✓3(b)9(c)8(c)∞
4e✓✓✓9(c)8(c)10(e)
5d✓✓✓9(c)✓10(e)
6z✓✓✓✓✓10(e)

Result

Shortest distance from a to z = 10.

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →