Past exam question: 2063 Baishakh (Regular / Back), Q7
Open in the Padhaiko appQuestion
What do you mean by shortest path? Write the Dijkstra's algorithm and explain the algorithm with suitable example.
Solution
Shortest Path & Dijkstra's Algorithm: In a weighted graph , a shortest path from source to target is a path whose sum of edge weights is minimum among all paths from to .
Algorithm DIJKSTRA(G = (V, E), w, src):
1. For each vertex v in V: dist[v] = INFINITY, visited[v] = FALSE
2. dist[src] = 0
3. For count = 1 to |V|:
Pick unvisited vertex u with smallest dist[u]
visited[u] = TRUE
For each neighbor v of u:
If !visited[v] and dist[u] + w(u, v) < dist[v]:
dist[v] = dist[u] + w(u, v)
4. Return distExample on Directed Graph (A->B(4), A->C(2), C->B(1), B->D(3), C->D(5)): From source A:
- Init:
dist = {A:0, B:inf, C:inf, D:inf}. PickA:dist[B]=4, dist[C]=2. - Pick
C(dist=2): relaxC->B:2+1=3 < 4dist[B]=3; relaxC->D:dist[D]=7. - Pick
B(dist=3): relaxB->D:3+3=6 < 7dist[D]=6. - Pick
D(dist=6): all vertices visited.
Shortest distances from A: A=0, C=2, B=3, D=6.
Answer:
A shortest path minimizes total edge weight between vertices. Dijkstra's algorithm greedily locks the closest unvisited vertex and relaxes outgoing edges, finding distances A=0, C=2, B=3, D=6 in the example.