Dijkstra’s Algorithm

Dijkstra’s algorithm is a popular algorithm created by Edsger W. Dijkstra in 1956 to find the shortest path between two vertices in a weighted graph, where edges have weight or distance which shows the distance/weight between two vertices. The algorithm has many applications in real world like in maps finding the shortest route between two locations, social networking applications, network routers where also a shortest path is searched, telephone networking and etc.

Dijkstra’s algorithm is a greedy algorithm which in each step finds the best solution and when we sum those solutions we find the best solution in general. The algorithm doesn’t work for edges with negative weights so in this case is used another algorithm which is called Bellman–Ford algorithm.

Let’s create an example weighted graph and explain how the algorithm works.

Let’s say we want to find the shortest path from vertex A to vertex F.

Initially we assign infinite value to all vertices as we don’t know the shortest distance to them. We assign 0 to starting vertex A as distance to self is 0.

We take the starting vertex A and we mark it as visited and then we observe all connected vertices and if the value of the visited vertex plus weight of the edge to the neighbor vertex is smaller than current value of the neighbor vertex then we update the neighbor vertex’s value with the weight of the edge plus value of the current visited vertex.

So in our example the value of A is 0 and the distance to B is 1.0. The current value of B is infinity.

(0 + 1.0) < infinity, then we update the value of B to 1.0

The value of A is 0 and the distance to C is 2.0. The current value of C is infinity.

(0 + 2.0) < infinity, then we update the value of C to 2.0

The next step is to chose which vertex to visit. The key point here is to take vertex with minimum value from unvisited vertices. In our case this is vertex B which has value 1.0 and it is less than the value of vertex C which is 2.0. From implementation point of view this is the point where we use priority queue. We enqueue vertices in a priority queue and then when we need the vertex with min value we just call dequeue and we get the minimum vertex.

So now we are on vertex B. We repeat the same operations here. We need to check the values of all unvisited neighbor vertices and update them if the current value + edge weight to neighbor vertex is smaller than neighbor vertex’s value. Be careful not to perform this operation to the visited neighbors.

So in our case B is connected to A and D. As A is already visited we will observe only D.

D’s current value is infinity, B’s current value is 1.0 and distance to D is 6.5.

(1.0 + 6.5) < infinity, then we update the value of D to 7.5

In the next step we take the vertex with min value from unvisited vertices. In our case this is vertex C

C (2.0) < D (7.5)

C has the following neighbors: A, E, D. From those neighbors only D and E are unvisited so we only observe them.

D has a value of 7.5. C has value of 2.0 and distance to D is 0.5.

(2.0 + 0.5) < 7.5, then we update the value of D to 2.5

E has value of infinity. C has value of 2.0 and the distance to E is 10.5

(2.0 + 10.5) < infinity, then we update the value of E to 12.5

In the next step we take the unvisited vertex with minimum value which is D.

D(2.5) < E(12.5)

D has the following neighbors: C, E, F. From those neighbors only E and F are unvisited so we only observe them.

E has value of 12.5. D has value of 2.5 and the distance to E is 2.0

(2.5 + 2.0) < 12.5, then we update the value of E to 4.5

F has value of infinity, D has value of 2.5 and the distance to F is 0.5

(2.5 + 0.5) < infinity, then we update the value of F to 3.0

Next we take the vertex with minimum value from unvisited vertices which is F.

F(3.0) < E(4.5)

F has two neighbors: D and E. From those neighbors only E is unvisited so we observe only E.

E has value of 4.5. D has value of 3.0 and the distance to E is 1.0

(3.0 + 1.0) < 4.5, then we update the value of E to 4.0

We have only one vertex which is unvisited, we visit vertex E. As all neighbors of E are already visited we are done with the algorithm at this stage. All vertices are visited and they have assigned values.

Note that in this graph example we had to always update the values of neighbor vertices but take into account if:

(current vertex’s value + distance from current to neighbor) > neighbor’s value

we don’t update the neighbor vertex’s value.

So looking into the initial graph where we applied Dijkstra’s algorithm we can say that the shortest path from A to F is: A–> C–> D–> F and the total distance is 3.0.

Implementation

Let’s have a look how we can implement Dijkstra’s algorithm with C# code. We we will use a priority queue which we explained in one of the previous articles here https://paircoders.com/2021/04/19/heap-priority-queue/

First we will create a Vertex class which will represent our vertices in the graph described above

    public class Vertex : IComparable<Vertex>
    {
        // We could have defined Vertex<T>
        // as generic to store any data inside
        // it, as you would probably do in
        // real world, here we miss it for
        // simplicity
        //public T Value { get; set; }

        public string Name { get; set; }
        public decimal Weight { get; set; }

        public bool IsVisited { get; set; }

        public Vertex Parent { get; set;  }

        public Vertex(string name)
        {
            this.Name = name;
        }

        public int CompareTo(Vertex other)
        {
            if (this.Weight < other.Weight)
                return -1;
            else if (this.Weight > other.Weight)
                return 1;
            else return 0;
        }
    }

We will keep a reference to the parent which last updated the current vertex’s value in order to be able to backtrack the shortest path for any given vertex.

Next we will create class Dijkstra

    public class Dijkstra
    {
        private List<Vertex> vertices;
        private decimal[][] adjMatrix;

        public Dijkstra(decimal[][] graph, List<Vertex> vertices)
        {
            if (graph.Length != vertices.Count)
            {
                throw new InvalidOperationException("Mismatch between graph and vertices");
            }

            this.adjMatrix = graph;
            this.vertices = vertices;
        }
   }

We use adjacency matrix to represent the graph, basically the two most popular approaches to represent a graph are adjacency matrix and adjacency list, you can learn more about this topic here https://www.geeksforgeeks.org/graph-and-its-representations/

Next we will add a method to Dijkstra class called ApplyDijkstra which will apply the algorithm.

        private void ApplyDijkstra(int source)
        {
            PriorityQueue<Vertex> pq =
                new PriorityQueue<Vertex>(PriroityQueueType.Min);

            // Initialize all vertices with infinite value
            foreach (var v in this.vertices)
            {
                v.Weight = decimal.MaxValue;
            }

            // Source vertex's distance to self is zero
            this.vertices[source].Weight = 0.0m;
            
            pq.Enqueue(this.vertices[source]);

            while (pq.Count() > 0)
            {
                // get the vertex with minimum wight
                // from unvisited vertices to process
                var minVertex = pq.Dequeue();
                minVertex.IsVisited = true;
                var minVIndex = vertices.IndexOf(minVertex);

                // Go trough all unvisited neighbors
                // and try to update their weight
                for (var i = 0; i < adjMatrix[minVIndex].Length; i++)
                {
                    // if weight is zero no connection between two vertices
                    if (this.adjMatrix[minVIndex][i] == 0.0m) continue;
                    // we are interested only in unvisited vertices
                    if (this.vertices[i].IsVisited) continue;

                    // calculate neighbor's weight by
                    // adding current weight and distance to the neighbor
                    // from current vertex
                    var calculatedWeight = adjMatrix[minVIndex][i] + minVertex.Weight;

                    // if calculated distance/weight is less then
                    // we found better path so update the neighbor's weight
                    if (calculatedWeight < this.vertices[i].Weight)
                    {
                        this.vertices[i].Weight = calculatedWeight;
                        this.vertices[i].Parent = minVertex;
                        // Add neighbor to the queue to process it later
                        pq.Enqueue(this.vertices[i]);
                    }
                }
            }
        }

With this method we traverse all vertices in vertices list and looking at the graph matrix we update the values of each vertex. Next we will add public method which takes source and destination parameters, applies the algorithm and then backtracks the shortest path from distance to source and last it returns an information about the shortest path and total distance.

        public string PrintShortestPath(string sourceName, string destinationName)
        {
            // We miss guard clauses for simplicity

            var sVert =
                vertices.First(v => v.Name == sourceName);

            int source =
                vertices.IndexOf(sVert);

            var dVert =
                vertices.First(v => v.Name == destinationName);

            int destination =
                vertices.IndexOf(dVert);

            // Calculate all vertices' weights
            ApplyDijkstra(source);

            var destinationVertex = vertices[destination];
            // Using stack to backtrack the path from
            // destination to source by iterating parents
            Stack<Vertex> backTrackShortestPath = new Stack<Vertex>();
            bool pathExists = false;
            while (destinationVertex != null)
            {
                if (destinationVertex.Name == sourceName)
                {
                    backTrackShortestPath.Push(destinationVertex);
                    pathExists = true;
                    break;
                }
                backTrackShortestPath.Push(destinationVertex);
                destinationVertex = destinationVertex.Parent;
            }

            if (!pathExists)
            {
                return $"No path exists from vertex:{source} to vertex:{destination}";
            }

            StringBuilder shortestPath = new StringBuilder();
            var currentWeightArrow = "";
            while (backTrackShortestPath.Count > 0)
            {
                var currentVertex = backTrackShortestPath.Pop();
                shortestPath.Append($"{currentWeightArrow}({currentVertex.Name})");
                currentWeightArrow = "--->";

            }

            shortestPath.AppendLine("\nTotal " +
                                    $"distance from vertex:{sourceName} " +
                                    $"to vertex:{destinationName} is " +
                                    $"{vertices[destination].Weight}");

            return shortestPath.ToString();
        }

Next let’s construct the graph we explained above and use the code above to find the shortest path

        static void Main(string[] args)
        {
            List<Vertex> vertices = new List<Vertex>
            {
                new Vertex("A"),
                new Vertex("B"),
                new Vertex("C"),
                new Vertex("D"),
                new Vertex("E"),
                new Vertex("F")
            };

            decimal[][] graph = {
                new[] { 0.0m, 1.0m, 2.0m, 0.0m, 0.0m, 0.0m },
                new[] { 1.0m, 0.0m, 0.0m, 6.5m, 0.0m, 0.0m },
                new[] { 2.0m, 0.0m, 0.0m, 0.5m, 10.5m, 0.0m },
                new[] { 0.0m, 6.5m, 0.5m, 0.0m, 2.0m, 0.5m },
                new[] { 0.0m, 0.0m, 10.5m, 2.0m, 0.0m, 1.0m },
                new[] { 0.0m, 0.0m, 0.0m, 0.5m, 1.0m, 0.0m }
            };

            var dijkstra = new Dijkstra(graph, vertices);

            var shortestPath = 
                dijkstra.PrintShortestPath("A", "F");

            Console.WriteLine("The shortest path:");

            Console.WriteLine(shortestPath);

            Console.ReadLine();
        }

The result in the console is:

The algorithm’s time complexity is

O(E Log V)

E – number of edges

V – number of vertices.

With this we conclude our explanation about Dijkstra’s algorithm. You can read more about the topic here:

https://www.programiz.com/dsa/dijkstra-algorithm

https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/