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 V = 4;
int source = 0;
List<(int, int)>[] graph = new List<(int, int)>[V];
for (int i = 0; i < V; i++) graph[i] = new List<(int, int)>();
graph[0].Add((1, 4));
graph[0].Add((2, 1));
graph[2].Add((1, 2));
graph[1].Add((3, 1));
graph[2].Add((3, 5));

int[] dist = new int[V];
for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[source] = 0;

var pq = new SortedSet<(int dist, int node)>(Comparer<(int dist, int node)>.Create((a, b) => a.dist != b.dist ? a.dist - b.dist : a.node - b.node));
pq.Add((0, source));

while (pq.Count > 0) {
    var current = pq.Min;
    pq.Remove(current);
    int u = current.node;
    foreach (var (v, w) in graph[u]) {
        if (dist[u] + w < dist[v]) {
            if (dist[v] != int.MaxValue) pq.Remove((dist[v], v));
            dist[v] = dist[u] + w;
            pq.Add((dist[v], v));
        }
    }
}

Console.WriteLine(string.Join(",", dist));

A [0, 3, 1, 5]

B [0, 4, 1, 6]

C [0, 3, 1, 4]

D [0, 2, 1, 3]

💡 Hint

Trace the shortest paths step-by-step from source 0 to all nodes.

Starting from node 0, the shortest path to node 2 is 1, to node 1 is via node 2 with total cost 3, and to node 3 is via node 1 with total cost 4.

🧠 Conceptual

intermediate

Understanding Priority Queue Role in Dijkstra's Algorithm

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

A To sort edges by their weights before processing.

B To store all nodes in alphabetical order.

C To keep track of visited nodes only.

D To always pick the node with the smallest current distance for exploration.

💡 Hint

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

The priority queue helps select the next node with the smallest tentative distance to ensure the shortest paths are found efficiently.

🔧 Debug

advanced

Identify the Bug in Dijkstra's Algorithm Implementation

What error will the following code produce when running Dijkstra's algorithm on a graph with 3 nodes and edges 0->1 (2), 1->2 (3)?

Code snippet:
int[] dist = new int[3]; for (int i = 0; i < 3; i++) dist[i] = int.MaxValue; dist[0] = 0; var pq = new SortedSet<(int dist, int node)>(); pq.Add((0, 0)); while (pq.Count > 0) { var current = pq.Min; pq.Remove(current); int u = current.node; foreach (var (v, w) in graph[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.Add((dist[v], v)); } } }

A Runtime error due to adding duplicate elements in SortedSet.

B Logical error: distances never update.

C No error, code runs correctly.

D Syntax error because of missing semicolons.

💡 Hint

Consider how SortedSet handles duplicate keys with same distance and node.

The code does not remove old entries from the priority queue before adding updated distances, causing duplicates and runtime errors.

🚀 Application

advanced

Applying Dijkstra's Algorithm to Find Shortest Path Count

Given a graph with edges:
0->1 (1), 0->2 (1), 1->3 (1), 2->3 (1)
How many shortest paths exist from node 0 to node 3?

A 1

B 2

C 4

D 3

💡 Hint

Count all distinct shortest routes from 0 to 3.

There are two shortest paths: 0->1->3 and 0->2->3, both with total cost 2.

🧠 Conceptual

expert

Why Dijkstra's Algorithm Fails with Negative Edge Weights

Why does Dijkstra's algorithm not work correctly if the graph contains 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 priority queue which does not support negative numbers.

D Because it only works on directed graphs.

💡 Hint

Think about the algorithm's assumption about shortest distances.

Dijkstra's algorithm assumes that once a node is visited with the smallest distance, no shorter path to it exists, which is false if negative edges exist.

Practice

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

easy

A. To find the minimum spanning tree of a graph

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

C. To detect cycles in a graph

D. To sort the vertices in topological order

Solution

1. Step 1: Understand the goal of Dijkstra's Algorithm

   Dijkstra's Algorithm is designed to find the shortest paths from one starting point (source) to all other points in a weighted graph.

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 a DAG. These are different goals.

3. Final Answer:

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

4. Quick Check:

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

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing shortest path with minimum spanning tree
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following C# code snippets correctly initializes the distance array for Dijkstra's Algorithm for a graph with 5 vertices?

easy

A. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = -1;

B. int[] dist = new int[5] {0, 0, 0, 0, 0};

C. int[] dist = new int[5]; dist.Fill(0);

D. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue;

Solution

1. Step 1: Understand initialization for Dijkstra's distances

   Distances are set to a very large number (infinity) initially, except the source vertex which is set to 0 later.

2. Step 2: Check each option

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; sets all distances to int.MaxValue, which is correct. int[] dist = new int[5] {0, 0, 0, 0, 0}; sets all to 0, which is wrong. int[] dist = new int[5]; dist.Fill(0); uses a non-existent Fill method. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = -1; sets distances to -1, which is invalid for distances.

3. Final Answer:

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; -> Option D

4. Quick Check:

   Initialize distances to max value [OK]

Hint: Use int.MaxValue to represent infinity distances [OK]

Common Mistakes:

• Setting all distances to zero initially
• Using negative values for distances
• Using non-existent array methods

3. Consider the following C# code snippet implementing Dijkstra's Algorithm on a graph with 4 vertices (0 to 3). What is the shortest distance from vertex 0 to vertex 3?

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

int V = 4;
int[] dist = new int[V];
bool[] sptSet = new bool[V];

for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[0] = 0;

for (int count = 0; count < V - 1; count++) {
  int u = -1;
  int minDist = int.MaxValue;
  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && dist[v] < minDist) {
      minDist = dist[v];
      u = v;
    }
  }
  sptSet[u] = true;

  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v]) {
      dist[v] = dist[u] + graph[u, v];
    }
  }
}

Console.WriteLine(dist[3]);

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace the algorithm's distance updates

   Start dist = [0, ∞, ∞, ∞]. - Pick vertex 0: update dist[1] = 1, dist[2] = 4. - Pick vertex 1 (dist=1): update dist[2] = min(4, 1+2=3) = 3, dist[3] = 1+6=7. - Pick vertex 2 (dist=3): update dist[3] = min(7, 3+3=6) = 6. - Pick vertex 3 (dist=6): done.

2. Step 2: Final shortest distance to vertex 3

   After all updates, dist[3] = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to vertex 3 = 6 [OK]

Hint: Update distances only if new path is shorter [OK]

Common Mistakes:

• Not updating distances when a shorter path is found
• Confusing vertex indices
• Ignoring zero-weight edges as no edge

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

int V = 3;
int[] dist = new int[V];
bool[] visited = new bool[V];

for (int i = 0; i < V; i++)
  dist[i] = int.MaxValue;
dist[0] = 0;

for (int count = 0; count < V; count++) {
  int u = 0;
  for (int v = 0; v < V; v++) {
    if (!visited[v] && dist[v] < dist[u])
      u = v;
  }
  visited[u] = true;
  // Update distances here (omitted)
}

medium

A. Variable u is initialized to 0 causing incorrect minimum selection

B. dist array is not initialized properly

C. visited array is not updated

D. Loop runs one time too many

Solution

1. Step 1: Analyze initialization of u in inner loop

   Variable u is set to 0 before checking for minimum dist among unvisited vertices. If dist[0] is int.MaxValue, comparison fails and minimum may not be found correctly.

2. Step 2: Correct approach for minimum selection

   u should be initialized to -1 or a sentinel, and updated only when a better candidate is found to avoid wrong minimum selection.

3. Final Answer:

   Variable u is initialized to 0 causing incorrect minimum selection -> Option A

4. Quick Check:

   Initialize u properly to find minimum dist [OK]

Hint: Initialize min index to -1 before searching minimum [OK]

Common Mistakes:

• Initializing min index to 0 without checking if visited
• Not updating visited array
• Incorrect loop count

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

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

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

hard

A. 7

B. 8

C. 6

D. 9

Solution

1. Step 1: Trace shortest paths from vertex 0

   Start dist = [0, ∞, ∞, ∞, ∞]. - From 0: dist[1] = 2, dist[2] = 4. - From 1: dist[2] = min(4, 2+1=3) = 3, dist[3] = 2+7=9. - From 2: dist[4] = 3+3=6. - From 3: dist[4] = min(6, 9+1=10) = 6.

2. Step 2: Final shortest distance to vertex 4

   The shortest distance to vertex 4 is 6 via path 0->1->2->4.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Shortest path distance to 4 = 6 [OK]

Hint: Check all paths and pick minimum sum of edges [OK]

Common Mistakes:

• Ignoring shorter indirect paths
• Adding edge weights incorrectly
• Assuming direct edge is always shortest