Skip to main content

Dijkstra shortest path (2072 Asoj)

Short answer

Dijkstra's algorithm gives a shortest path length of 12 along a–b–e–z.

Use Dijkstra's algorithm to find the length of shortest path in the following weighted graph. Also highlight the shortest path/paths in the graph. [Figure: weighted graph on vertices a, b, c, d, e, z with edges a-b 2, a-c 3, b-c 5, b-e 7, c-e 10, c-d 8, e-d 6, e-z 3, 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–b 2, a–c 3, b–c 5, b–e 7, c–e 10, c–d 8, e–d 6, e–z 3, d–z 4.

Trace

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

StepFixedabcdez
1a02(a)3(a)∞∞∞
2b✓2(a)3(a)∞9(b)∞
3c✓✓3(a)11(c)9(b)∞
4e✓✓✓11(c)9(b)12(e)
5d✓✓✓11(c)✓12(e)
6z✓✓✓✓✓12(e)

Result

Shortest distance from a to z = 12.

Shortest path (highlight these edges): a → b → e → z with edge weights 2 + 7 + 3 = 12.

Answer: shortest path length = 12 along a → b → e → z (2 + 7 + 3).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →