Algorithms, Software Development

Dijkstra’s Algorithm: A Beginner’s Guide

by Walter S.

Have you ever used a GPS to find the quickest route to your destination? If so, you’ve likely benefited from the work of a brilliant computer scientist named Edsger Dijkstra. In 1956, he developed an algorithm that finds the shortest path between two nodes in a graph. Today, we’ll explore Dijkstra’s Algorithm and then dive into an example to help you visualize and implement this useful tool.

Imagine you have a road map that shows cities (nodes) connected by highways (edges). Each highway has a length (weight), representing the distance between the cities. You want to find the shortest path from one city to another.

Dijkstra’s Algorithm helps you do just that by following these simple steps:

  1. Start by setting the distance of the starting city to 0 and the distance of all other cities to infinity.
  2. Create a list of unvisited cities, initially containing all cities.
  3. Choose the city with the smallest distance from the starting city (it’ll be the starting city itself in the first step).
  4. For each neighbor of the chosen city, calculate the distance from the starting city through the chosen city to the neighbor.
  5. If the calculated distance is less than the current distance to the neighbor, update the neighbor’s distance.
  6. Mark the chosen city as visited and remove it from the list of unvisited cities.
  7. Repeat steps 3 to 6 until all cities have been visited or the destination city has been visited.

Implementing Dijkstra’s Algorithm in C#

Let’s start by creating a simple Graph class that will represent our road map. Each city will be represented as an integer and the distances between cities will be stored in a 2D array called adjacencyMatrix.

public class Graph
{
    public int VerticesCount;
    public int[,] adjacencyMatrix;

    public Graph(int verticesCount)
    {
        VerticesCount = verticesCount;
        adjacencyMatrix = new int[verticesCount, verticesCount];
    }

    public void AddEdge(int source, int destination, int weight)
    {
        adjacencyMatrix[source, destination] = weight;
        adjacencyMatrix[destination, source] = weight;
    }
}

Now, let’s implement Dijkstra’s Algorithm in a method called FindShortestPath. This method will take a Graph object, a starting city, and a destination city as input, and return an array containing the shortest path distances from the starting city to all other cities.

public static int[] FindShortestPath(Graph graph, int startNode)
{
    int[] distances = new int[graph.VerticesCount];
    bool[] visited = new bool[graph.VerticesCount];

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

    distances[startNode] = 0;

    for (int i = 0; i < graph.VerticesCount - 1; i++)
    {
        int minDistanceNode = -1;

        for (int j = 0; j < graph.VerticesCount; j++)
        {
            if (!visited[j] && (minDistanceNode == -1 || distances[j] < distances[minDistanceNode]))
            {
                minDistanceNode = j;
            }
        }

        visited[minDistanceNode] = true;

        for (int j = 0; j < graph.VerticesCount; j++)
        {
            int edgeDistance = graph.adjacencyMatrix[minDistanceNode, j];

            if (edgeDistance > 0 && !visited[j])
            {
                int newDistance = distances[minDistanceNode] + edgeDistance;

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

    return distances;
}

Now, let’s create a simple console app to test our implementation:

public static void Main(string[] args)
{
    Graph graph = new Graph(5);

    graph.AddEdge(0, 1, 10);
    graph.AddEdge(0, 2, 5);
    graph.AddEdge(1, 3, 1);
    graph.AddEdge(1, 2, 2);
    graph.AddEdge(2, 1, 3);
    graph.AddEdge(2, 3, 9);
    graph.AddEdge(2, 4, 2);
    graph.AddEdge(3, 4, 4);
    graph.AddEdge(4, 0, 7);
    graph.AddEdge(4, 3, 6);

    int startNode = 0;
    int[] shortestPathDistances = FindShortestPath(graph, startNode);

    for (int i = 0; i < shortestPathDistances.Length; i++)
    {
        Console.WriteLine($"Distance from node {startNode} to node {i} is {shortestPathDistances[i]}");
    }
}

When you run this code, you’ll see the shortest path distances from the starting city (node 0) to all other cities:

Distance from node 0 to node 0 is 0
Distance from node 0 to node 1 is 8
Distance from node 0 to node 2 is 5
Distance from node 0 to node 3 is 9
Distance from node 0 to node 4 is 7

Remember that this algorithm is versatile and can be applied to various problems, from route planning to network routing and beyond.