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

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other city by always traveling to the nearest city you haven't visited yet.

Start: A (source)
Graph:
A --2--> B
A --5--> C
B --1--> C
C --3--> D
D --1--> E

Dry Run Walkthrough

Input: Graph with edges: A->B(2), A->C(5), B->C(1), C->D(3), D->E(1); start at A

Goal: Find shortest distances from A to all nodes

Step 1: Initialize distances: A=0, B=∞, C=∞, D=∞, E=∞; mark all unvisited

Distances: A=0, B=∞, C=∞, D=∞, E=∞; Unvisited: {A,B,C,D,E}

Why: We start with source distance zero and others unknown

Step 2: Visit A; update neighbors B and C distances: B=2, C=5

Distances: A=0(visited), B=2, C=5, D=∞, E=∞; Unvisited: {B,C,D,E}

Why: From A, we can reach B and C with weights 2 and 5

Step 3: Choose unvisited node with smallest distance: B=2; visit B; update C: min(5, 2+1=3)=3

Distances: A=0, B=2(visited), C=3, D=∞, E=∞; Unvisited: {C,D,E}

Why: B is closest unvisited; update C distance via B

Step 4: Choose C=3; visit C; update D: D=3+3=6

Distances: A=0, B=2, C=3(visited), D=6, E=∞; Unvisited: {D,E}

Why: From C, we can reach D with total distance 6

Step 5: Choose D=6; visit D; update E: E=6+1=7

Distances: A=0, B=2, C=3, D=6(visited), E=7; Unvisited: {E}

Why: From D, we can reach E with total distance 7

Step 6: Choose E=7; visit E; no neighbors to update

Distances: A=0, B=2, C=3, D=6, E=7(visited); Unvisited: {}

Why: All nodes visited; algorithm ends

Result:

Final distances: A=0 -> B=2 -> C=3 -> D=6 -> E=7

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private readonly Dictionary<string, List<(string, int)>> adj = new();

    public void AddEdge(string from, string to, int weight) {
        if (!adj.ContainsKey(from)) adj[from] = new List<(string, int)>();
        adj[from].Add((to, weight));
        if (!adj.ContainsKey(to)) adj[to] = new List<(string, int)>();
    }

    public Dictionary<string, int> Dijkstra(string start) {
        var dist = new Dictionary<string, int>();
        var visited = new HashSet<string>();
        var pq = new SortedSet<(int dist, string node)>(Comparer<(int, string)>.Create((a,b) => a.dist != b.dist ? a.dist - b.dist : string.Compare(a.node, b.node)));

        foreach (var node in adj.Keys) {
            dist[node] = int.MaxValue;
        }
        dist[start] = 0;
        pq.Add((0, start));

        while (pq.Count > 0) {
            var current = pq.Min;
            pq.Remove(current);
            string u = current.node;
            if (visited.Contains(u)) continue;
            visited.Add(u);

            foreach (var (v, w) in adj[u]) {
                if (!visited.Contains(v) && dist[u] + w < dist[v]) {
                    if (pq.Contains((dist[v], v))) pq.Remove((dist[v], v));
                    dist[v] = dist[u] + w;
                    pq.Add((dist[v], v));
                }
            }
        }
        return dist;
    }
}

class Program {
    static void Main() {
        var graph = new Graph();
        graph.AddEdge("A", "B", 2);
        graph.AddEdge("A", "C", 5);
        graph.AddEdge("B", "C", 1);
        graph.AddEdge("C", "D", 3);
        graph.AddEdge("D", "E", 1);

        var distances = graph.Dijkstra("A");
        foreach (var kvp in distances) {
            Console.WriteLine($"Distance from A to {kvp.Key} is {kvp.Value}");
        }
    }
}

dist[start] = 0; pq.Add((0, start));

Initialize start node distance to zero and add to priority queue

var current = pq.Min; pq.Remove(current); string u = current.node; if (visited.Contains(u)) continue; visited.Add(u);

Select closest unvisited node and mark visited

foreach (var (v, w) in adj[u]) { if (!visited.Contains(v) && dist[u] + w < dist[v]) { if (pq.Contains((dist[v], v))) pq.Remove((dist[v], v)); dist[v] = dist[u] + w; pq.Add((dist[v], v)); } }

Update distances of neighbors if shorter path found and update priority queue

Output

Distance from A to A is 0

Distance from A to B is 2

Distance from A to C is 3

Distance from A to D is 6

Distance from A to E is 7

Complexity Analysis

Time: O(E log V) because each edge is checked and priority queue operations take log V time

Space: O(V + E) because we store graph edges and distance info for each node

vs Alternative: Compared to Bellman-Ford (O(VE)), Dijkstra is faster on graphs with non-negative weights

Edge Cases

Graph with no edges

Distances to all nodes except start remain infinity

DSA C#

dist[start] = 0;

Graph with single node

Distance to start node is zero, no other nodes to update

DSA C#

dist[start] = 0;

Graph with unreachable nodes

Distances to unreachable nodes remain infinity

DSA C#

if (!visited.Contains(v) && dist[u] + w < dist[v])

When to Use This Pattern

When asked to find shortest paths from one point to all others in a weighted graph without negative edges, use Dijkstra's algorithm because it efficiently finds minimum distances.

Common Mistakes

Mistake: Not updating the priority queue after distance changes
Fix: Remove old distance entry and add updated distance to priority queue to keep it accurate

Mistake: Visiting nodes multiple times without marking visited
Fix: Use a visited set to avoid processing nodes more than once

Summary

Finds shortest distances from one start node to all others in a weighted graph without negative edges.

Use when you need efficient shortest paths from a single source in graphs with non-negative weights.

Always pick the closest unvisited node next and update neighbors to find shortest paths step by step.

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