Past exam question: 2066 Bhadra (Regular / Back), Q12
Open in the Padhaiko appQuestion
Use Dijkstra's algorithm to find the shortest path from node A to other nodes given in the graph.
[figure: directed weighted graph on 7 vertices A, B, C, D, E, F, G with directed edges A->B(10), A->C(3), B->C(4), C->B(1), B->D(2), C->D(8), C->E(2), D->E(9), E->D(7), F->D(2), F->E(8), G->E(4)]
Solution
Initialization (Source A): Set dist[A] = 0 and all other distances to : dist = {A: 0, B: inf, C: inf, D: inf, E: inf, F: inf, G: inf}.
Relaxation Table (Pick Minimum Unvisited Vertex at Each Iteration):
| Selected | A | B | C | D | E | F | G | Relaxations |
|---|---|---|---|---|---|---|---|---|
| Init | 0 | — | ||||||
A (0) | 0 | 10 | 3 | B=10 (via A), C=3 (via A) | ||||
C (3) | 0 | 4 | 3 | 11 | 5 | B=3+1=4, D=3+8=11, E=3+2=5 | ||
B (4) | 0 | 4 | 3 | 6 | 5 | D=min(11, 4+2)=6 | ||
E (5) | 0 | 4 | 3 | 6 | 5 | E->D: 5+7=12 > 6 (no change) | ||
D (6) | 0 | 4 | 3 | 6 | 5 | D->E: 6+9=15 > 5 (no change) |
Vertices F and G have zero incoming edges from {A, B, C, D, E}, so they remain unreachable ().
Answer:
Shortest path distances and paths from A:
- A A:
0 - A C:
3(pathA -> C) - A B:
4(pathA -> C -> B) - A E:
5(pathA -> C -> E) - A D:
6(pathA -> C -> B -> D) - A F, A G: (unreachable; no incoming edges from
{A..E})