Dijkstra's Algorithm Single Source Shortest Path in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of Dijkstra's Algorithm?

To find the shortest path from a single starting point (source) to all other points (nodes) in a graph with non-negative edge weights.

intermediate

In Dijkstra's Algorithm, what data structure is commonly used to select the next node with the smallest tentative distance?

A priority queue (often implemented as a min-heap) is used to efficiently pick the node with the smallest current distance.

intermediate

Why can't Dijkstra's Algorithm handle graphs with negative edge weights?

Because it assumes that once a node's shortest distance is found, it won't change. Negative edges can create shorter paths later, breaking this assumption.

advanced

What is the time complexity of Dijkstra's Algorithm when using a priority queue and adjacency list?

O((V + E) log V), where V is the number of vertices and E is the number of edges.

beginner

Explain the role of the 'distance' array in Dijkstra's Algorithm.

It keeps track of the shortest known distance from the source node to every other node, updating as shorter paths are found.

What does Dijkstra's Algorithm compute?

A Minimum spanning tree

B All pairs shortest paths

C Shortest paths from one source to all nodes

D Topological sort

Dijkstra's Algorithm finds the shortest paths from a single source node to all other nodes.

Which data structure helps efficiently pick the next node with the smallest distance in Dijkstra's Algorithm?

A Priority queue

B Queue

C Stack

D Linked list

A priority queue allows quick access to the node with the smallest tentative distance.

Can Dijkstra's Algorithm work correctly with negative edge weights?

A Yes, always

B No, never

C Only if no negative cycles exist

D Only if the graph is directed

Dijkstra's Algorithm does not handle negative edge weights correctly.

What is updated when a shorter path to a node is found during the algorithm?

A The node's adjacency list

B The node's color

C The node's degree

D The node's distance value

The distance array is updated with the new shorter distance.

What is the initial distance value for the source node in Dijkstra's Algorithm?

A Zero

B Infinity

C Negative one

D Undefined

The source node distance is set to zero because the distance from the source to itself is zero.

Describe step-by-step how Dijkstra's Algorithm finds the shortest paths from a source node.

Think about how you explore nodes and update distances.

Explain why Dijkstra's Algorithm cannot handle negative edge weights and what could happen if it tries.

Consider what happens if a shorter path appears after visiting a node.

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