PadhaikoAll subjects

Past exam question: 2066 Bhadra (Regular / Back), Q12

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

Topic: Graphs

Question

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):

SelectedABCDEFGRelaxations
Init0—
A (0)0103B=10 (via A), C=3 (via A)
C (3)043115B=3+1=4, D=3+8=11, E=3+2=5
B (4)04365D=min(11, 4+2)=6
E (5)04365E->D: 5+7=12 > 6 (no change)
D (6)04365D->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:

All past exam questions for Data Structure and Algorithms