Dijkstra shortest path (2074 Bhadra)

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

Reading: the outer arc A–D has weight 12 and the outer arc C–Z has weight 11; the other eight edges are as listed.

Edges: A–B 6, A–C 8, B–C 6, B–D 7, B–E 5, C–D 10, C–E 9, D–E 5, D–Z 5, E–Z 8, A–D 12, C–Z 11.

Trace

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

Result

Shortest distance from A to Z = 17.

Shortest path (highlight these edges): A → D → Z with edge weights 12 + 5 = 17.

Answer: length of the shortest path A to Z = 17, along A–D–Z (the direct edge A–D = 12, then D–Z = 5). The route A–B–E–Z costs 19 and A–C–Z costs 19.