Dijkstra's Algorithm Single Source Shortest Path in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance vector with infinity.

DSA C++

vector<int> dist(V, [1]);

Drag options to blanks, or click blank then click option'

AINT_MAX

B-1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing distances to 0 will make the algorithm think all nodes are at zero distance.

Using -1 can cause incorrect comparisons.

We initialize distances to all vertices as infinity (INT_MAX) to represent unknown distances.

2fill in blank

medium

Complete the code to pick the vertex with the minimum distance not yet processed.

DSA C++

int u = minDistance(dist, [1]);

Drag options to blanks, or click blank then click option'

Asource

BV

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Passing the graph or source instead of the visited array.

Passing the number of vertices instead of the visited array.

The function minDistance needs the visited array to ignore already processed vertices.

3fill in blank

hard

Fix the error in the relaxation step condition to update distances correctly.

DSA C++

if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[v] [1] (dist[u] + graph[u][v])) {
    dist[v] = dist[u] + graph[u][v];
}

Drag options to blanks, or click blank then click option'

A==

B>

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' causes no updates.

Using '==' or '!=' causes wrong logic.

We update dist[v] only if the new path is shorter, so dist[u] + weight < dist[v]. The condition uses > to check if current dist[v] is greater than new distance.

4fill in blank

hard

Fill both blanks to correctly initialize and update the priority queue for Dijkstra's algorithm.

DSA C++

priority_queue<pair<int, int>, vector<pair<int, int>>, [1]> pq;
pq.push([2], source});

Drag options to blanks, or click blank then click option'

Agreater<pair<int, int>>

Bless<pair<int, int>>

Cdist[source]

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using less<pair<int,int>> creates a max-heap, which is incorrect.

Pushing dist[source] which is INT_MAX initially instead of 0.

Dijkstra's algorithm uses a min-heap priority queue, so we use greater<pair<int,int>> to get the smallest distance first. The initial distance pushed is 0 for the source.

5fill in blank

hard

Fill all three blanks to correctly update distances and push neighbors into the priority queue.

DSA C++

if (dist[u] + graph[u][v] [1] dist[v]) {
    dist[v] = dist[u] + graph[u][v];
    pq.[2]([3], v);
}

Drag options to blanks, or click blank then click option'

A<

Bpush

Cdist[v]

D>

Epop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' in the condition.

Using pq.pop instead of pq.push.

Pushing the wrong distance value.

We update dist[v] if the new path is shorter (dist[u] + weight < dist[v]). Then we push the updated distance and vertex into the priority queue.

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To find the shortest path from a single source to all other vertices

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distances from one starting point (source) to every other point in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option D

4. Quick Check:

   Dijkstra's Algorithm = shortest paths from source [OK]

Hint: Remember: Dijkstra finds shortest paths from one source [OK]

Common Mistakes:

• Confusing Dijkstra with algorithms for max flow
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance array in Dijkstra's Algorithm in C++?

easy

A. vector<int> dist(n, -1); dist[source] = 0;

B. vector<int> dist(n, INT_MAX); dist[source] = 0;

C. vector<int> dist(n, 0); dist[source] = INT_MAX;

D. vector<int> dist(n); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as infinity (or a very large number) to represent unknown distance.

2. Step 2: Check each option

   vector<int> dist(n, INT_MAX); dist[source] = 0; correctly sets all distances to INT_MAX and source distance to 0. Others either set wrong initial values or leave uninitialized.

3. Final Answer:

   vector<int> dist(n, INT_MAX); dist[source] = 0; -> Option B

4. Quick Check:

   Distance array initialized with INT_MAX except source = 0 [OK]

Hint: Initialize all distances to max except source zero [OK]

Common Mistakes:

• Setting all distances to zero initially
• Not setting source distance to zero
• Leaving distance array uninitialized

3. Consider the following graph edges and weights:

0 -> 1 (4), 0 -> 2 (1), 2 -> 1 (2), 1 -> 3 (1), 2 -> 3 (5)

If we run Dijkstra's Algorithm from source vertex 0, what is the shortest distance array after completion?

medium

A. [0, 3, 1, 4]

B. [0, 4, 1, 6]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Initialize distances

   Start with dist = [0, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1] = 4, dist[2] = 1. From 2: dist[1] = min(4, 1+2=3) = 3, dist[3] = 1+5=6. From 1: dist[3] = min(6, 3+1=4) = 4.

3. Final Answer:

   [0, 3, 1, 4] -> Option A

4. Quick Check:

   Shortest distances from 0 = [0,3,1,4] [OK]

Hint: Update distances by relaxing edges with minimum sums [OK]

Common Mistakes:

• Not updating distance to vertex 1 via vertex 2
• Incorrectly summing edge weights
• Ignoring better paths found later

4. The following C++ code snippet for Dijkstra's Algorithm has a bug. What is the error?

vector<int> dist(n, INT_MAX);
dist[source] = 0;
priority_queue> pq;
pq.push({0, source});
while(!pq.empty()) {
  int u = pq.top().second;
  int d = pq.top().first;
  pq.pop();
  if(d > dist[u]) continue;
  for(auto &edge : graph[u]) {
    int v = edge.first;
    int w = edge.second;
    if(dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      pq.push({dist[v], v});
    }
  }
}

medium

A. priority_queue is max-heap by default (needs negative distances or greater comparator)

B. Distance array is not initialized correctly

C. The graph adjacency list is not iterated properly

D. The source distance is not set to zero

Solution

1. Step 1: Check priority queue usage

   In C++, priority_queue by default is max-heap. To get min-heap behavior for distances, distances should be pushed as negative or use greater comparator.

2. Step 2: Identify the bug

   The code pushes distances as positive values, so the smallest distance won't be on top, causing incorrect behavior.

3. Final Answer:

   priority_queue is max-heap by default (needs negative distances or greater comparator) -> Option A

4. Quick Check:

   Use negative distances or min-heap for correct priority queue [OK]

Hint: Use negative distances or min-heap to get smallest distance first [OK]

Common Mistakes:

• Ignoring priority queue ordering behavior
• Not setting source distance to zero
• Incorrect graph iteration

5. You have a weighted graph with 5 vertices and edges:

0->1(10), 0->4(5), 1->2(1), 2->3(4), 4->1(3), 4->2(9), 4->3(2), 3->0(7)

Using Dijkstra's Algorithm from source 0, what is the shortest distance to vertex 3?

hard

A. 13

B. 15

C. 7

D. 18

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1]=10, dist[4]=5. From 4: dist[1]=min(10,5+3=8)=8, dist[2]=min(INF,5+9=14)=14, dist[3]=min(INF,5+2=7)=7. From 1: dist[2]=min(14,8+1=9)=9. From 2: dist[3]=min(7,9+4=13)=7.

3. Step 3: Final shortest distance to vertex 3

   The shortest distance to vertex 3 is 7.

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Shortest distance to vertex 3 = 7 [OK]

Hint: Relax edges in order, update distances with minimum sums [OK]

Common Mistakes:

• Not updating distances via vertex 4
• Ignoring better paths through intermediate vertices
• Confusing edge weights