Dijkstra's Algorithm Single Source Shortest Path in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dijkstra's Algorithm on a Simple Graph

What is the output distances array after running Dijkstra's algorithm from source node 0 on the following graph?

Graph edges:
0 -> 1 (weight 4), 0 -> 2 (weight 1), 2 -> 1 (weight 2), 1 -> 3 (weight 1), 2 -> 3 (weight 5)

Assume nodes are 0-indexed and graph has 4 nodes.

DSA C++

int V = 4;
vector<pair<int,int>> adj[V];
adj[0].push_back({1,4});
adj[0].push_back({2,1});
adj[2].push_back({1,2});
adj[1].push_back({3,1});
adj[2].push_back({3,5});

vector<int> dist(V, INT_MAX);
dist[0] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,0});

while(!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    if(d > dist[u]) continue;
    for(auto &edge : adj[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});
        }
    }
}

for(int i=0; i<V; i++) {
    cout << dist[i] << " ";
}

A [0, 3, 1, 4]

B [0, 4, 1, 5]

C [0, 3, 1, 6]

D [0, 2, 1, 4]

💡 Hint

Trace the shortest path updates from source 0 step-by-step.

Starting from node 0, the shortest distances are updated as follows: dist[0]=0, dist[2]=1 (via 0->2), dist[1]=3 (via 0->2->1), dist[3]=4 (via 0->2->1->3).

🧠 Conceptual

intermediate

Understanding Dijkstra's Algorithm Behavior

Which of the following statements about Dijkstra's algorithm is always true when used on a graph with non-negative edge weights?

A It uses a stack data structure to store nodes to visit next.

B It works correctly even if the graph has negative weight edges.

C It finds the shortest path from the source to all other nodes.

D It guarantees the shortest path in graphs with cycles only if the cycles have zero weight.

💡 Hint

Recall the conditions for Dijkstra's algorithm correctness.

Dijkstra's algorithm finds the shortest path from the source to all nodes if all edge weights are non-negative. It does not work correctly with negative weights. It uses a priority queue, not a stack.

🔧 Debug

advanced

Identify the Bug in Dijkstra's Algorithm Implementation

Consider this snippet from a Dijkstra's algorithm implementation. What is the bug causing incorrect shortest path results?

Code snippet:
for (auto &edge : adj[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({dist[u], v}); } }

A The priority queue push uses dist[u] instead of dist[v].

B The condition should be dist[u] > dist[v] + w.

C The adjacency list is accessed incorrectly; should be adj[v].

D The loop should iterate over pq, not adj[u].

💡 Hint

Check what value is pushed into the priority queue after updating dist[v].

After updating dist[v], the new distance dist[v] must be pushed into the priority queue, not dist[u]. Using dist[u] causes wrong priority and incorrect results.

❓ Predict Output

advanced

Output Distances with a Larger Graph

What is the output distances array after running Dijkstra's algorithm from source node 0 on this graph with 5 nodes?

Edges:
0->1 (10), 0->4 (5), 1->2 (1), 1->4 (2), 2->3 (4), 3->2 (6), 4->1 (3), 4->2 (9), 4->3 (2)

Print distances array after algorithm completes.

DSA C++

int V = 5;
vector<pair<int,int>> adj[V];
adj[0].push_back({1,10});
adj[0].push_back({4,5});
adj[1].push_back({2,1});
adj[1].push_back({4,2});
adj[2].push_back({3,4});
adj[3].push_back({2,6});
adj[4].push_back({1,3});
adj[4].push_back({2,9});
adj[4].push_back({3,2});

vector<int> dist(V, INT_MAX);
dist[0] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0,0});

while(!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    if(d > dist[u]) continue;
    for(auto &edge : adj[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});
        }
    }
}

for(int i=0; i<V; i++) {
    cout << dist[i] << " ";
}

A [0, 8, 10, 7, 5]

B [0, 8, 9, 7, 5]

C [0, 10, 11, 9, 5]

D [0, 5, 14, 7, 5]

💡 Hint

Calculate shortest paths stepwise from node 0.

The shortest distances are: 0->0=0, 0->4=5, 0->1=8 (via 4), 0->3=7 (via 4), 0->2=9 (via 1).

🧠 Conceptual

expert

Dijkstra's Algorithm Limitations and Alternatives

Which of the following statements correctly describes a limitation of Dijkstra's algorithm and a suitable alternative?

A Dijkstra's algorithm finds all paths; A* algorithm finds only the longest path.

B Dijkstra's algorithm is inefficient for dense graphs; Floyd-Warshall algorithm is faster for sparse graphs.

C Dijkstra's algorithm works only on directed graphs; Prim's algorithm is used for undirected graphs.

D Dijkstra's algorithm cannot handle negative edge weights; Bellman-Ford algorithm is used instead.

💡 Hint

Think about edge weights and algorithm applicability.

Dijkstra's algorithm fails with negative edge weights because it assumes once a node is visited with shortest distance, it won't be updated. Bellman-Ford handles negative weights correctly.

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