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 shortest distance array output after running Dijkstra's algorithm from source node 0 on the following graph?

Graph edges with weights:

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

DSA C

int graph[4][4] = {
  {0, 4, 1, 0},
  {0, 0, 0, 1},
  {0, 2, 0, 5},
  {0, 0, 0, 0}
};

// Run Dijkstra from node 0
// Output shortest distances array

A [0, 2, 1, 3]

B [0, 4, 1, 5]

C [0, 3, 1, 4]

D [0, 3, 2, 4]

💡 Hint

Remember to update distances when a shorter path is found through a neighbor.

Starting at node 0, distance to itself is 0. Distance to node 2 is 1. From node 2, distance to node 1 is 1+2=3, which is less than direct 4. From node 1, distance to node 3 is 3+1=4, which is less than 0->2->3 (1+5=6). So final distances: [0,3,1,4].

🧠 Conceptual

intermediate

Understanding Priority Queue Role in Dijkstra's Algorithm

Why is a priority queue used in Dijkstra's algorithm?

A To always pick the next node with the smallest tentative distance to process

B To store all nodes in alphabetical order

C To keep track of visited nodes only

D To reverse the order of nodes before processing

💡 Hint

Think about how the algorithm decides which node to explore next.

Dijkstra's algorithm picks the node with the smallest current distance to ensure shortest paths are found efficiently. A priority queue helps select this node quickly.

🔧 Debug

advanced

Identify the Error in Dijkstra's Algorithm Implementation

What error will this code cause when running Dijkstra's algorithm on a graph with 3 nodes?

int dist[3] = {0, INT_MAX, INT_MAX};
int visited[3] = {0, 0, 0};

for (int i = 0; i < 3; i++) {
  int u = -1;
  for (int j = 0; j < 3; j++) {
    if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
      u = j;
    }
  }
  visited[u] = 1;
  for (int v = 0; v < 3; v++) {
    if (graph[u][v] && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

A No error, code runs correctly

B Runtime error due to accessing dist[-1] if all nodes visited

C Syntax error due to missing semicolon

D Logic error: distances never updated

💡 Hint

What happens if all nodes are visited before the loop ends?

If all nodes are visited, u remains -1. Then visited[u] = 1 tries to access visited[-1], causing runtime error.

❓ Predict Output

advanced

Output of Dijkstra's Algorithm on a Graph with Zero-Weight Edges

What is the shortest distance array after running Dijkstra's algorithm from source node 0 on this graph?

Graph edges:

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

DSA C

int graph[4][4] = {
  {0, 0, 4, 0},
  {0, 0, 2, 5},
  {0, 0, 0, 1},
  {0, 0, 0, 0}
};

// Run Dijkstra from node 0
// Output shortest distances array

A [0, 0, 2, 5]

B [0, 0, 4, 5]

C [0, 2, 4, 5]

D [0, 0, 2, 3]

💡 Hint

Zero-weight edges can reduce distances without cost.

From 0 to 1 is 0, then 1 to 2 is 2, total 2. From 2 to 3 is 1, total 3. Direct 0 to 2 is 4, which is longer. So distances: [0,0,2,3].

🧠 Conceptual

expert

Why Dijkstra's Algorithm Fails with Negative Edge Weights

Why does Dijkstra's algorithm not work correctly if the graph has negative edge weights?

A Because it assumes once a node's shortest distance is found, it cannot be improved later

B Because it cannot handle graphs with cycles

C Because it uses a stack instead of a queue internally

D Because it requires all edges to have the same weight

💡 Hint

Think about how the algorithm finalizes distances.

Dijkstra's algorithm finalizes the shortest distance to a node when it is first selected. Negative edges can later provide a shorter path, which the algorithm does not reconsider, causing incorrect results.

Practice

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

easy

A. To sort the vertices of a graph topologically

B. To find the minimum spanning tree of a graph

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 goal of Dijkstra's Algorithm

   Dijkstra's Algorithm is designed to find the shortest distance 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

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection finds loops, and topological sort orders vertices in directed acyclic graphs. These are different goals.

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: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• 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. int dist[V]; for(int i=0; i

B. int dist[V] = {INT_MAX};

C. int dist[V] = {0};

D. int dist[V] = NULL;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (or a very large number) except the source vertex, to represent unknown shortest paths.

2. Step 2: Check each option

   int dist[V] = {0}; initializes all distances to 0, which is incorrect. int dist[V]; for(int i=0; i

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize distances to INT_MAX with loop [OK]

Hint: Use loop to set all distances to INT_MAX [OK]

Common Mistakes:

• Using {INT_MAX} initializes only first element
• Setting all distances to 0
• Assigning NULL to int array

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on the following graph represented by adjacency matrix?

int graph[4][4] = {
  {0, 1, 4, 0},
  {1, 0, 2, 6},
  {4, 2, 0, 3},
  {0, 6, 3, 0}
};

medium

A. [0, 1, 4, 7]

B. [0, 1, 3, 5]

C. [0, 1, 3, 6]

D. [0, 2, 4, 6]

Solution

1. Step 1: Initialize distances and start from vertex 0

   Distances: dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞. Update neighbors of 0: dist[1]=1, dist[2]=4.

2. Step 2: Pick vertex with smallest tentative distance and update neighbors

   Pick vertex 1 (dist=1). Update dist[2] = min(4, 1+2=3) = 3, dist[3] = min(∞, 1+6=7) = 7. Next pick vertex 2 (dist=3). Update dist[3] = min(7, 3+3=6) = 6. Finally pick vertex 3 (dist=6).

3. Final Answer:

   [0, 1, 3, 6] -> Option C

4. Quick Check:

   Distances after relaxation = [0,1,3,6] [OK]

Hint: Relax edges stepwise, pick smallest distance vertex next [OK]

Common Mistakes:

• Not updating distances after relaxation
• Choosing wrong next vertex
• Ignoring shorter paths through intermediate vertices

4. Identify the error in the following snippet of Dijkstra's Algorithm in C:

for (int count = 0; count < V-1; count++) {
  int u = minDistance(dist, sptSet);
  sptSet[u] = 1;
  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence

C. The sptSet array should be initialized with 1 instead of 0

D. The dist[u] check should be 'dist[u] == INT_MAX' instead of '!='

Solution

1. Step 1: Analyze edge existence condition

   The condition 'graph[u][v]' relies on implicit truthiness of non-zero values. In C, this works but is less clear. Using 'graph[u][v] != 0' explicitly checks for edge presence and improves readability.

2. Step 2: Check other conditions

   Loop range from 0 to V-1 is correct for V vertices. sptSet should start with 0 (false). The dist[u] check must be '!= INT_MAX' to ensure u is reachable before relaxing edges.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence -> Option B

4. Quick Check:

   Explicit edge check improves clarity [OK]

Hint: Use explicit '!= 0' to check edges in adjacency matrix [OK]

Common Mistakes:

• Assuming loop range is wrong
• Initializing sptSet incorrectly
• Reversing dist[u] check logic

5. Given a weighted graph with vertices 0 to 5 and edges:

0-1: 7, 0-2: 9, 0-5: 14, 1-2: 10, 1-3: 15, 2-3: 11, 2-5: 2, 3-4: 6, 4-5: 9

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

hard

A. 20

B. 26

C. 21

D. 19

Solution

1. Step 1: Initialize distances and start from vertex 0

   dist[0]=0, others = ∞. Update neighbors: dist[1]=7, dist[2]=9, dist[5]=14.

2. Step 2: Pick vertex with smallest dist and update neighbors

   Pick 1 (7): update dist[3] = min(∞, 7+15=22) = 22. Pick 2 (9): update dist[3] = min(22, 9+11=20) = 20, dist[5] = min(14, 9+2=11) = 11. Pick 5 (11): update dist[4] = min(∞, 11+9=20) = 20. Pick 3 (20): update dist[4] = min(20, 20+6=26) = 20. Pick 4 (20).

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Shortest path to 4 = 20 [OK]

Hint: Relax edges carefully, update shortest distances stepwise [OK]

Common Mistakes:

• Not updating dist[5] to smaller value
• Ignoring shorter path through vertex 2
• Adding edges incorrectly