Past exam question: 2065 Shrawan (Regular / Back), Q10
Open in the Padhaiko appQuestion
Explain Dijkstra's algorithm for finding sortest path with the help of an algorithm.
Solution
Principle of Dijkstra's Algorithm: Dijkstra's algorithm solves the single-source shortest path problem on weighted graphs with non-negative edge weights (). It maintains a tentative distance dist[v] for every vertex and greedily finalizes the unvisited vertex u with minimum dist[u], relaxing all outgoing edges .
Algorithm DIJKSTRA(G, src):
Algorithm DIJKSTRA(G = (V, E), w, src):
1. For each vertex v in V:
dist[v] = INFINITY
visited[v] = FALSE
parent[v] = NULL
2. dist[src] = 0
3. Repeat |V| times:
a) Pick unvisited vertex u with minimum dist[u]
b) Mark visited[u] = TRUE
c) For each neighbor v of u (edge u -> v with weight w(u, v)):
If !visited[v] and dist[u] + w(u, v) < dist[v]:
dist[v] = dist[u] + w(u, v)
parent[v] = u
4. Return dist, parent
Time complexity: with an array, or with a min-heap priority queue.
Answer:
Dijkstra's algorithm greedily selects the unvisited vertex with smallest tentative distance dist[u] and relaxes all outgoing edges via dist[v] = min(dist[v], dist[u] + w(u, v)), finding single-source shortest paths for non-negative weights.