Dijkstra's Algorithm Single Source Shortest Path in DSA C# - Deep Dive

Overview - Dijkstra's Algorithm Single Source Shortest Path

What is it?

Dijkstra's Algorithm finds the shortest path from one starting point to all other points in a network or graph. It works by exploring paths step-by-step, always choosing the closest unvisited point next. This helps find the quickest way to reach every destination from the start. It is widely used in maps, routing, and network analysis.

Why it matters

Without Dijkstra's Algorithm, finding the shortest routes in complex networks would be slow and error-prone. Imagine trying to find the fastest way home without a map or GPS; it would take much longer and be frustrating. This algorithm makes navigation efficient and reliable, saving time and resources in real life and technology.

Where it fits

Before learning Dijkstra's Algorithm, you should understand basic graph concepts like nodes, edges, and weights. After mastering it, you can explore more advanced shortest path algorithms like A* or Bellman-Ford, and graph optimization techniques.

Mental Model

Core Idea

Always pick the closest unvisited point and update the shortest paths to its neighbors until all points are visited.

Think of it like...

Imagine you are in a city and want to visit all nearby places starting from your home. You always go to the closest place you haven't visited yet, and from there, you check if you can find shorter ways to other places. Step by step, you map out the quickest routes to everywhere.

Start (S)
  |
  v
[Visited Node] ---(edge weight)---> [Neighbor Node]
  |
  v
Repeat picking the closest unvisited node and update distances

Graph example:

  (S)
  /  \
 5    2
 /      \
(A)----3-->(B)

Distances updated stepwise from S to A and B.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Weights

Concept: Introduce graphs as points connected by lines with costs (weights).

A graph is a collection of points called nodes or vertices. These nodes are connected by lines called edges. Each edge has a number called weight that shows the cost or distance to travel that edge. For example, in a city map, intersections are nodes and roads are edges with distances as weights.

Result

You can represent a network of places and distances as a graph with weighted edges.

Understanding graphs and weights is essential because Dijkstra's Algorithm works by comparing these weights to find the shortest paths.

2

Foundation

Representing Graphs in Code

Concept: Learn how to store graphs using adjacency lists for efficient traversal.

In code, graphs are often stored as adjacency lists: each node keeps a list of neighbors and the cost to reach them. For example, a dictionary where keys are nodes and values are lists of (neighbor, weight) pairs. This structure makes it easy to explore neighbors and update distances.

Result

You can efficiently access neighbors and their weights for any node in the graph.

Choosing the right graph representation affects how fast and simple the algorithm runs.

3

Intermediate

Tracking Distances and Visited Nodes

Concept: Introduce distance arrays and visited sets to keep track of progress.

We keep an array or dictionary to store the shortest known distance from the start to each node. Initially, distances are infinite except the start node which is zero. We also keep a set of visited nodes to avoid reprocessing. As we explore, we update distances and mark nodes visited.

Result

You can track which nodes are processed and the best distances found so far.

Maintaining these structures ensures the algorithm progresses correctly and avoids loops.

4

Intermediate

Choosing the Next Node to Visit

🤔Before reading on: do you think picking any unvisited node or the closest unvisited node leads to correct shortest paths? Commit to your answer.

Concept: Always select the unvisited node with the smallest current distance to explore next.

At each step, pick the unvisited node with the smallest distance value. This ensures we explore the closest nodes first, which is key to finding shortest paths. Using a priority queue (min-heap) helps efficiently find this node.

Result

The algorithm explores nodes in order of increasing distance from the start.

Choosing the closest unvisited node first guarantees that once a node is visited, its shortest path is finalized.

5

Intermediate

Updating Neighbor Distances

🤔Before reading on: when you find a shorter path to a neighbor, should you update its distance immediately or wait until later? Commit to your answer.

Concept: When visiting a node, update distances to its neighbors if a shorter path is found.

For each neighbor of the current node, calculate the total distance through the current node. If this is less than the neighbor's known distance, update it. This step spreads the shortest path information through the graph.

Result

Distances to neighbors get shorter as better paths are found.

Updating neighbors' distances is how the algorithm propagates shortest path information step-by-step.

6

Advanced

Implementing with Priority Queue in C#

🤔Before reading on: do you think a simple list or a priority queue is better for selecting the next node? Commit to your answer.

Concept: Use a priority queue to efficiently select the next closest node during the algorithm.

In C#, use a PriorityQueue where Node is the graph node and int is the distance. Enqueue the start node with distance 0. At each step, dequeue the node with the smallest distance. Update neighbors and enqueue them if their distance improves. This keeps selection fast even for large graphs.

Result

The algorithm runs efficiently, quickly finding shortest paths even in big graphs.

Using a priority queue reduces the time complexity from O(V^2) to O((V+E) log V), making the algorithm practical for real-world use.

7

Expert

Handling Graphs with Negative or Zero Weights

🤔Before reading on: do you think Dijkstra's Algorithm works correctly with negative edge weights? Commit to your answer.

Concept: Dijkstra's Algorithm assumes all edge weights are non-negative; negative weights break correctness.

If a graph has negative weights, Dijkstra's Algorithm can produce wrong results because it assumes once a node is visited, its shortest path is final. Negative weights can create shorter paths after visiting. For such graphs, algorithms like Bellman-Ford are used instead.

Result

Dijkstra's Algorithm fails or gives incorrect paths if negative weights exist.

Knowing the algorithm's assumptions prevents misuse and guides choosing the right algorithm for the problem.

Under the Hood

Dijkstra's Algorithm maintains a set of nodes with known shortest distances and a priority queue to pick the next closest node. When a node is visited, its shortest path is finalized because any other path would be longer. The algorithm updates neighbors' distances by relaxing edges, ensuring the shortest path tree grows outward from the start node.

Why designed this way?

The algorithm was designed to efficiently find shortest paths in graphs with non-negative weights by exploiting the greedy choice of the closest node. Alternatives like Bellman-Ford handle negative weights but are slower. Dijkstra's method balances speed and correctness for many practical cases like road maps.

Start Node (distance=0)
   |
   v
[Priority Queue]
   |
   v
Pick closest node -> Update neighbors' distances
   |
   v
Mark node visited -> Repeat until all nodes visited

Graph edges relaxed stepwise:

(S) --5--> (A)
 |          |
 2          3
 |          |
 v          v
(B)        (C)

Distances updated and nodes visited in order.

Myth Busters - 3 Common Misconceptions

Quick: Does Dijkstra's Algorithm work correctly with negative edge weights? Commit yes or no.

Common Belief: Dijkstra's Algorithm works with any edge weights, including negative ones.

Reality: Dijkstra's Algorithm only works correctly if all edge weights are zero or positive.

Why it matters: Using it on graphs with negative weights can produce wrong shortest paths, leading to incorrect routing or decisions.

Quick: Once a node is visited in Dijkstra's Algorithm, can its shortest path change later? Commit yes or no.

Common Belief: A node's shortest path can change after it is visited if a better path is found.

Reality: Once a node is visited (extracted from the priority queue), its shortest path is final and will not change.

Why it matters: This property allows the algorithm to be efficient and guarantees correctness; misunderstanding it can cause incorrect implementations.

Quick: Is it okay to pick any unvisited node next instead of the closest one? Commit yes or no.

Common Belief: You can pick any unvisited node next and still get correct shortest paths.

Reality: You must always pick the unvisited node with the smallest current distance to ensure correctness.

Why it matters: Picking nodes out of order can lead to wrong paths and incorrect results.

Expert Zone

1

The priority queue may contain multiple entries for the same node with different distances; only the first extracted is valid, others are ignored.

2

Dijkstra's Algorithm can be adapted to find shortest paths in directed or undirected graphs with minor changes.

3

Using adjacency matrices instead of lists increases time complexity, making the algorithm slower on large sparse graphs.

When NOT to use

Avoid Dijkstra's Algorithm when graphs have negative edge weights or require path counting. Use Bellman-Ford for negative weights or A* for heuristic-guided shortest paths.

Production Patterns

In real-world systems like GPS navigation, Dijkstra's Algorithm is combined with heuristics (A*) and pre-processing to speed up queries. Network routing protocols use variants to update paths dynamically.

Connections

Bellman-Ford Algorithm

Alternative shortest path algorithm that handles negative weights.

Understanding Dijkstra's limitations helps appreciate why Bellman-Ford is needed for graphs with negative edges.

Priority Queue Data Structure

Core data structure used to efficiently select the next node.

Mastering priority queues improves understanding of Dijkstra's performance and implementation.

Supply Chain Logistics

Both involve finding optimal routes and minimizing costs.

Knowing how shortest path algorithms work helps optimize real-world delivery and transportation networks.

Common Pitfalls

#1 Using Dijkstra's Algorithm on graphs with negative edge weights.

Wrong approach:

RunDijkstra(graphWithNegativeEdges, startNode);

Correct approach:

RunBellmanFord(graphWithNegativeEdges, startNode);

Root cause:

Misunderstanding that Dijkstra's Algorithm requires non-negative weights for correctness.

#2 Selecting the next node to visit without using a priority queue or picking the closest node.

Wrong approach:

foreach (var node in unvisited) { if (node.distance < currentMin) currentMin = node.distance; } // but pick any node instead

Correct approach:

Use PriorityQueue to always dequeue the node with smallest distance.

Root cause:

Not using an efficient data structure leads to incorrect order and slower performance.

#3 Not updating neighbor distances when a shorter path is found.

Wrong approach:

if (newDistance >= distances[neighbor]) { /* do nothing */ }

Correct approach:

if (newDistance < distances[neighbor]) { distances[neighbor] = newDistance; enqueue neighbor; }

Root cause:

Failing to relax edges prevents the algorithm from finding the true shortest paths.

Key Takeaways

Dijkstra's Algorithm finds shortest paths by always exploring the closest unvisited node next.

It requires all edge weights to be zero or positive to guarantee correct results.

Using a priority queue is essential for efficient selection of the next node to visit.

Once a node is visited, its shortest path is finalized and will not change.

Understanding its assumptions and limitations helps choose the right algorithm for different graph problems.

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