Dijkstra's Algorithm Single Source Shortest Path in DSA C# - Execution Trace

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Set source distance = 0

↓

Add all nodes to unvisited set

↓

While unvisited nodes remain

↓

Select node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < current distance

↓

Update distance and predecessor

↓

Mark current node visited

↓

Repeat until all nodes visited

↓

Result: shortest distances from source

Dijkstra's algorithm finds shortest paths from one node to all others by repeatedly selecting the closest unvisited node and updating neighbors.

Execution Sample

DSA C#

graph = {
  'A': {'B': 4, 'C': 1},
  'B': {'E': 4},
  'C': {'B': 2, 'D': 4},
  'D': {'E': 4},
  'E': {}
}
distances = Dijkstra(graph, 'A')

This code runs Dijkstra's algorithm on a small graph starting from node A to find shortest paths.

Execution Table

Step	Operation	Current Node	Distances	Unvisited Set	Visual State
1	Initialize distances	None	{A:0, B:∞, C:∞, D:∞, E:∞}	{A,B,C,D,E}	A(0) B(∞) C(∞) D(∞) E(∞)
2	Select node with smallest distance	A	{A:0, B:∞, C:∞, D:∞, E:∞}	{A,B,C,D,E}	A(0) B(∞) C(∞) D(∞) E(∞)
3	Update neighbors of A	A	{A:0, B:4, C:1, D:∞, E:∞}	{A,B,C,D,E}	A(0) B(4) C(1) D(∞) E(∞)
4	Mark A visited	A	{A:0, B:4, C:1, D:∞, E:∞}	{B,C,D,E}	A(0) B(4) C(1) D(∞) E(∞)
5	Select node with smallest distance	C	{A:0, B:4, C:1, D:∞, E:∞}	{B,C,D,E}	A(0) B(4) C(1) D(∞) E(∞)
6	Update neighbors of C	C	{A:0, B:3, C:1, D:5, E:∞}	{B,C,D,E}	A(0) B(3) C(1) D(5) E(∞)
7	Mark C visited	C	{A:0, B:3, C:1, D:5, E:∞}	{B,D,E}	A(0) B(3) C(1) D(5) E(∞)
8	Select node with smallest distance	B	{A:0, B:3, C:1, D:5, E:∞}	{B,D,E}	A(0) B(3) C(1) D(5) E(∞)
9	Update neighbors of B	B	{A:0, B:3, C:1, D:5, E:7}	{B,D,E}	A(0) B(3) C(1) D(5) E(7)
10	Mark B visited	B	{A:0, B:3, C:1, D:5, E:7}	{D,E}	A(0) B(3) C(1) D(5) E(7)
11	Select node with smallest distance	D	{A:0, B:3, C:1, D:5, E:7}	{D,E}	A(0) B(3) C(1) D(5) E(7)
12	Update neighbors of D	D	{A:0, B:3, C:1, D:5, E:7}	{D,E}	A(0) B(3) C(1) D(5) E(7)
13	Mark D visited	D	{A:0, B:3, C:1, D:5, E:7}	{E}	A(0) B(3) C(1) D(5) E(7)
14	Select node with smallest distance	E	{A:0, B:3, C:1, D:5, E:7}	{E}	A(0) B(3) C(1) D(5) E(7)
15	Mark E visited	E	{A:0, B:3, C:1, D:5, E:7}	{}	A(0) B(3) C(1) D(5) E(7)
16	All nodes visited	None	{A:0, B:3, C:1, D:5, E:7}	{}	Final distances

💡 All nodes visited, shortest distances finalized

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	Final
Distances	{A:0, B:∞, C:∞, D:∞, E:∞}	{A:0, B:4, C:1, D:∞, E:∞}	{A:0, B:3, C:1, D:5, E:∞}	{A:0, B:3, C:1, D:5, E:7}	{A:0, B:3, C:1, D:5, E:7}	{A:0, B:3, C:1, D:5, E:7}	{A:0, B:3, C:1, D:5, E:7}
Unvisited Set	{A,B,C,D,E}	{A,B,C,D,E}	{B,C,D,E}	{B,D,E}	{D,E}	{E}	{}
Current Node	None	A	C	B	D	E	None

Key Moments - 3 Insights

Why do we update the distance of a neighbor only if the new distance is smaller?

Because Dijkstra's algorithm always keeps the shortest known distance. If the new distance is not smaller, it means we already have a better path, so no update is needed. See execution_table rows 3, 6, and 9 where distances are updated only when smaller.

Why do we mark a node as visited after processing it?

Marking a node visited means we have found the shortest path to it and won't revisit it. This prevents infinite loops and redundant checks. Look at execution_table rows 4, 7, 10, 13, and 15 where nodes are marked visited after updating neighbors.

Why do we select the unvisited node with the smallest distance each time?

Selecting the closest unvisited node ensures we explore paths in order of increasing distance, guaranteeing shortest paths. This is shown in execution_table rows 2, 5, 8, 11, and 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 6. What is the distance to node B after updating neighbors of C?

A 4

B 3

C 1

D 5

💡 Hint

Check the Distances column at step 6 in the execution_table.

At which step does node B get marked as visited?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look for 'Mark B visited' operation in the execution_table.

If the edge from C to D had weight 1 instead of 4, how would the distance to D change after step 6?

A It would become 2

B It would remain ∞

C It would become 5

D It would become 4

💡 Hint

Calculate new distance: distance to C (1) + edge weight (1) = 2, check variable_tracker after step 6.

Concept Snapshot

Dijkstra's Algorithm:
- Finds shortest paths from one source node to all others
- Initialize distances: source=0, others=∞
- Repeatedly pick unvisited node with smallest distance
- Update neighbors if shorter path found
- Mark node visited after processing
- Ends when all nodes visited, distances finalized

Full Transcript

Dijkstra's algorithm starts by setting the distance to the source node as zero and all others as infinity. It keeps a set of unvisited nodes. In each step, it selects the unvisited node with the smallest known distance. Then, it checks all neighbors of this node and updates their distances if a shorter path is found through the current node. After updating neighbors, the current node is marked as visited, meaning its shortest distance is finalized. This process repeats until all nodes are visited. The final distances represent the shortest paths from the source to every other node in the graph.

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