Skip to main content

Dijkstra shortest path (2070 Magh)

Short answer

The shortest path length from a to z is 17, via a–b–d–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-c 3, a-b 6, c-b 4, c-e 11, b-e 8, b-d 7, e-d 5, e-z 10, d-z 4]

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

Trace

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

StepFixedabcdez
1a06(a)3(a)∞∞∞
2c✓6(a)3(a)∞14(c)∞
3b✓6(a)✓13(b)14(c)∞
4d✓✓✓13(b)14(c)17(d)
5e✓✓✓✓14(c)17(d)
6z✓✓✓✓✓17(d)

Result

Shortest distance from a to z = 17.

Shortest path (highlight these edges): a → b → d → z with edge weights 6 + 7 + 4 = 17.

Answer: shortest path length = 17 along a → b → d → z (6 + 7 + 4). By comparison, the route a–c–e–z costs 3 + 11 + 10 = 24.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →