Implementing Dijkstra's Algorithm in C#

Introduction

Dijkstra's algorithm is a classic algorithm in computer science that is used to find the shortest paths between nodes in a graph. Named after its creator, Edsger W. Dijkstra, this algorithm is widely used in various applications such as network routing, geographic mapping, and even in game development. In this article, we will delve into the workings of Dijkstra's algorithm and provide a detailed implementation in C#. By the end, we will understand Dijkstra's Algorithm to efficiently find the shortest paths in a weighted graph using this powerful algorithm.

Dijkstra's algorithm works on both directed and undirected graphs with non-negative weights. The primary objective of the algorithm is to find the shortest path from a single source node to all other nodes in the graph. It maintains a set of unvisited nodes and continuously selects the node with the smallest tentative distance, updating the distances of its neighboring nodes accordingly.

Key Concepts

Graph Representation: A graph consists of nodes (vertices) connected by edges, each with an associated weight (cost or distance).
Priority Queue: The algorithm uses a priority queue (often implemented with a min-heap) to efficiently select the node with the smallest distance.
Distance Array: An array that holds the shortest known distance from the source to each node, initialized to infinity except for the source node.

Dijkstra's Algorithm in C#

To implement Dijkstra's algorithm in C#, we will follow these steps:

Define a class to represent the graph.
Implement the algorithm to compute the shortest paths.
Test the implementation with a sample graph.

Step 1. Graph Representation

Define a class Graph to represent the graph. This class will use an adjacency list to store the nodes and their corresponding edges.

using System;
using System.Collections.Generic;

public class Graph
{
    private int vertices;
    private List<Tuple<int, int>>[] adjacencyList;

    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjacencyList = new List<Tuple<int, int>>[vertices];

        for (int i = 0; i < vertices; i++)
        {
            adjacencyList[i] = new List<Tuple<int, int>>();
        }
    }

    public void AddEdge(int u, int v, int weight)
    {
        adjacencyList[u].Add(new Tuple<int, int>(v, weight));
    }

    public List<Tuple<int, int>>[] GetAdjacencyList()
    {
        return adjacencyList;
    }
}

Step 2. Implementing Dijkstra's Algorithm

The Dijkstra method will take the graph and the source node as input and output the shortest distances to all other nodes.

using System.Linq;
using System;

public class DijkstraAlgorithm
{
    public static int[] Dijkstra(Graph graph, int source)
    {
        int vertices = graph.GetAdjacencyList().Length;
        int[] distances = new int[vertices];
        bool[] shortestPathTreeSet = new bool[vertices];

        for (int i = 0; i < vertices; i++)
        {
            distances[i] = int.MaxValue;
            shortestPathTreeSet[i] = false;
        }

        distances[source] = 0;

        for (int count = 0; count < vertices - 1; count++)
        {
            int u = MinimumDistance(distances, shortestPathTreeSet);
            shortestPathTreeSet[u] = true;

            foreach (var neighbor in graph.GetAdjacencyList()[u])
            {
                int v = neighbor.Item1;
                int weight = neighbor.Item2;

                if (!shortestPathTreeSet[v] && distances[u] != int.MaxValue && distances[u] + weight < distances[v])
                {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        return distances;
    }

    private static int MinimumDistance(int[] distances, bool[] shortestPathTreeSet)
    {
        int min = int.MaxValue, minIndex = -1;

        for (int v = 0; v < distances.Length; v++)
        {
            if (!shortestPathTreeSet[v] && distances[v] <= min)
            {
                min = distances[v];
                minIndex = v;
            }
        }

        return minIndex;
    }
}

Step 3. Testing the Implementation

We will create a sample graph and test the Dijkstra's algorithm implementation.

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(5);
        graph.AddEdge(0, 1, 10);
        graph.AddEdge(0, 4, 5);
        graph.AddEdge(1, 2, 1);
        graph.AddEdge(1, 4, 2);
        graph.AddEdge(2, 3, 4);
        graph.AddEdge(3, 0, 7);
        graph.AddEdge(3, 2, 6);
        graph.AddEdge(4, 1, 3);
        graph.AddEdge(4, 2, 9);
        graph.AddEdge(4, 3, 2);

        int source = 0;
        int[] distances = DijkstraAlgorithm.Dijkstra(graph, source);

        Console.WriteLine("Vertex\tDistance from Source");
        for (int i = 0; i < distances.Length; i++)
        {
            Console.WriteLine($"{i}\t{distances[i]}");
        }
    }
}

Step 4. Output

Output

Conclusion

Dijkstra's algorithm is an essential tool for finding the shortest paths in weighted graphs. In this article, we explored the fundamental concepts of Dijkstra's algorithm and provided a step-by-step implementation in C#. Understanding and implementing this algorithm can significantly enhance your ability to solve complex problems in various fields, from network routing to game development. By leveraging the power of Dijkstra's algorithm, you can optimize pathfinding in your applications and ensure efficient data processing.