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.