PadhaikoAll subjects

Past exam question: 2065 Shrawan (Regular / Back), Q10

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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.

All past exam questions for Data Structure and Algorithms