PadhaikoAll subjects

Past exam question: 2063 Baishakh (Regular / Back), Q7

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Graphs

Question

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 dist

Example on Directed Graph (A->B(4), A->C(2), C->B(1), B->D(3), C->D(5)): From source A:

  1. Init: dist = {A:0, B:inf, C:inf, D:inf}. Pick A: dist[B]=4, dist[C]=2.
  2. Pick C (dist=2): relax C->B: 2+1=3 < 4 dist[B]=3; relax C->D: dist[D]=7.
  3. Pick B (dist=3): relax B->D: 3+3=6 < 7 dist[D]=6.
  4. 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.

All past exam questions for Data Structure and Algorithms