Dijkstra's Algorithm Single Source Shortest Path in DSA C# - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working as a city planner. You have a map of intersections connected by roads with distances. You want to find the shortest distance from a starting intersection to all other intersections.

🎯 Goal: Build a program that uses Dijkstra's algorithm to find the shortest path distances from a given start intersection to all others in the city map.

📋 What You'll Learn

Create a graph representation using a dictionary with adjacency lists

Add a variable to hold the number of intersections

Implement Dijkstra's algorithm to find shortest distances

Print the shortest distances from the start intersection

💡 Why This Matters

🌍 Real World

City planners and GPS navigation systems use shortest path algorithms like Dijkstra's to find the quickest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is important for software engineers working on mapping, routing, network optimization, and logistics applications.

1

Create the graph data structure

Create a dictionary called graph where keys are integers representing intersections 0 to 4, and values are lists of tuples representing connected intersections and distances. Use these exact connections:
0: [(1, 10), (2, 3)], 1: [(2, 1), (3, 2)], 2: [(1, 4), (3, 8), (4, 2)], 3: [(4, 7)], 4: [(3, 9)]

DSA C#

// Create the graph dictionary with adjacency lists
// Your code here

Hint

Use a Dictionary<int, List<(int, int)>> to store the graph. Each key is an intersection number. Each value is a list of tuples with connected intersection and distance.

2

Add the number of intersections variable

Add an integer variable called numIntersections and set it to 5 to represent the total intersections in the graph.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{(1, 10), (2, 3)}},
            {1, new List{(2, 1), (3, 2)}},
            {2, new List{(1, 4), (3, 8), (4, 2)}},
            {3, new List{(4, 7)}},
            {4, new List{(3, 9)}}
        };
        // Add numIntersections variable below
        // Your code here
    }
}

Hint

Just add int numIntersections = 5; inside the Main method after the graph.

3

Implement Dijkstra's algorithm

Implement Dijkstra's algorithm inside the Main method. Create an integer array distances of size numIntersections initialized with int.MaxValue. Set distances[0] to 0 as the start intersection is 0. Use a HashSet<int> called visited to track visited intersections. Loop until all intersections are visited: find the unvisited intersection with the smallest distance, mark it visited, then update distances of its neighbors if a shorter path is found.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{(1, 10), (2, 3)}},
            {1, new List{(2, 1), (3, 2)}},
            {2, new List{(1, 4), (3, 8), (4, 2)}},
            {3, new List{(4, 7)}},
            {4, new List{(3, 9)}}
        };
        int numIntersections = 5;

        // Implement Dijkstra's algorithm below
        // Your code here
    }
}

Hint

Initialize distances with int.MaxValue, set start distance to 0. Use a loop to pick the closest unvisited intersection, mark it visited, and update neighbors' distances if shorter paths are found.

4

Print the shortest distances

Add a for loop to print the shortest distances from intersection 0 to all intersections. Use Console.WriteLine with the format: "Distance from 0 to {i} is {distances[i]}" where i is the intersection number.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary> graph = new Dictionary>
        {
            {0, new List{(1, 10), (2, 3)}},
            {1, new List{(2, 1), (3, 2)}},
            {2, new List{(1, 4), (3, 8), (4, 2)}},
            {3, new List{(4, 7)}},
            {4, new List{(3, 9)}}
        };
        int numIntersections = 5;

        int[] distances = new int[numIntersections];
        for (int i = 0; i  visited = new HashSet();

        while (visited.Count < numIntersections)
        {
            int current = -1;
            int minDistance = int.MaxValue;
            for (int i = 0; i < numIntersections; i++)
            {
                if (!visited.Contains(i) && distances[i] < minDistance)
                {
                    minDistance = distances[i];
                    current = i;
                }
            }

            if (current == -1) break;

            visited.Add(current);

            foreach (var (neighbor, weight) in graph[current])
            {
                if (!visited.Contains(neighbor) && distances[current] + weight < distances[neighbor])
                {
                    distances[neighbor] = distances[current] + weight;
                }
            }
        }

        // Print shortest distances below
        for (int i = 0; i < numIntersections; i++)
        {
            Console.WriteLine($"Distance from 0 to {i} is {distances[i]}");
        }
    }
}

Hint

Use a for loop from 0 to numIntersections - 1 and print each distance with Console.WriteLine.

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