Dijkstra’s Algorithm

Dijkstra Algorithm is a graph algorithm for finding the shortest path from a source node to all other nodes in a graph(single source shortest path).

It is a type of greedy algorithm. It only works on weighted graphs with positive weights. It has a time complexity of $O(V^2)$ using the adjacency matrix representation of graph. The time complexity can be reduced to $O((V+E)logV)$ using adjacency list representation of graph, where E is the number of edges in the graph and V is the number of vertices in the graph.

Working of Dijkstra’s Algorithm

Highlights:

1. Greedy Algorithm
2. Relaxation

Dijkstra's Algorithm requires a graph and source vertex to work.The algorithm is purely based on greedy approach and thus finds the locally optimal choice(local minima in this case) at each step of the algorithm.

In this algorithm each vertex will have two properties defined for it-

• Visited property:-
  • This property represents whether the vertex has been visited or not.
  • We are using this property so that we don’t revisit a vertex.
  • A vertex is marked visited only after the shortest path to it has been found.
• Path property:-
  • This property stores the value of the current minimum path to the vertex. Current minimum path means the shortest way in which we have reached this vertex till now.
  • This property is updated whenever any neighbour of the vertex is visited.
  • The path property is important as it will store the final answer for each vertex.

Initially all the vertices are marked unvisited as we have not visited any of them. Path to all the vertices is set to infinity excluding the source vertex. Path to the source vertex is set to zero(0).

Then we pick the source vertex and mark it visited. After that all the neighbours of the source vertex are accessed and relaxation is performed on each vertex. Relaxation is the process of trying to lower the cost of reaching a vertex using another vertex.

In relaxation, the path of each vertex is updated to the minimum value amongst the current path of the node and the sum of the path to the previous node and the path from the previous node to this node.

Assume that p[v] is the current path value for node v,
p[n] is the path value upto the previously visited node n, and w is the weight of the edge between the curent node and previously visited node(edge weight between v and n)

Mathematically, relaxation can be represented as:
$$ p[v]=minimum(p[v] , p[n] + w) $$

Then in every subsequent step, an unvisited vertex with the least path value is marked visited and its neighbour’s paths are updated.

The above process is repeated till all the vertices in the graph are marked visited.

If any of the vertex is not reachable(disconnected component), its path remains infinity. If the source itself is a disconected component, then the path to all other vertices remains infinity.

Algorithm

1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node, lets say C.
3. For each neighbour N of the current node C: add the current distance of C with the weight of the edge connecting C-N. If it is smaller than the current distance of N, set it as the new current distance of N.
4. Mark the current node C as visited.
5. Go to step 2 if there are any nodes are unvisited.

Dijkstra Algorithm Example

Lets take an example to understand the algortihm better.

Lets assume the below graph as our input with the vertex A being the source.

• Initially all the vertices are marked unvisited.
• The path to A is 0 and for all the other vertices it is set to infinity.
• Now the source vertex A is marked as visited.Then its neighbours are accessed (only accessed and not visited).
• The path to B is updated to 4 using relaxation as the path to A is 0 and path from A to B is 4, so min((0+4),∞) is 4.
• The path to C is updated to 5 using relaxation as the path to A is 0 and path from A to C is 5, so min((0+5),∞) is 5. Both the neighbours of A are relaxed so we move ahead.
• Then the next unvisited vertex with least path is picked and mark it visited. So vertex B is now visited and its unvisited neighbours are relaxed. After relaxing path to C remains 5, path to E becomes 11 and path to D becomes 13.
• Then vertex C is picked and mark it visited and its unvisited neighbour E is relaxed. While relaxing E, we find that the path to E via C is smaller than its current path, so the path to E is updated to 8. All neighbours of C are now relaxed.
• Vertex E is picked and mark it visited and its neighbours D and F are relaxed. Path to D remains 13 and path to F becomes 14(8+6).
• Then vertex D is picked and mark it visited and only F is relaxed. The path to vertex F remains 14.
• Now only vertex F is remaining so it is visited but no relaxations are performed as all of its neighbours are already visited.
• As soon as all the vertices become visited the program stops.

The final paths we get are:

• $$ A=0(source) $$
• $$ B=4(A->B) $$
• $$ C=5(A->C) $$
• $$ D=13(A->B->D) $$
• $$ E=8(A->C->E) $$
• $$ F=14(A->C->E->F) $$

Psuedocode

function Dijkstra(Graph, source):
  for each vertex v in Graph:
    distance[v] = infinity

 distance[source] = 0
 G = the set of all nodes of the Graph

 while G is non-empty:
     Q = node in G with the least dist[ ]
     mark Q visited
     for each neighbor N of Q:
         alt_dist = distance[Q] + dist_between(Q, N)
         if alt-dist < distance[N]
             distance[N] := alt_dist

 return distance[ ]

This the pseudocode for Dijkstra's algorithm.

We get the minimum path to each vertex from the source vertex in the distance array.

Implementations for Dijkstra's Algorithm

1. Implementation of Dijkstra Algorithm in C++

#include <iostream>
using namespace std;
#include <limits.h>

#define V 6 // Number of vertices in the graph

//Function to find the vertex with minimum distance
int minDist(int dist[], bool sptSet[])
{

    // Initialize min value
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    return min_index;
}

//Function to print the constructed distance array
void printSolution(int distance[])
{
    cout <<"Vertex \t Distance from Source" << endl;
    for (int i = 0; i < V; i++)
        cout  << (char)(i+65) << " \t\t"<<distance[i]<< endl;
}

// Function that implements Dijkstra's algorithm
void dijkstra(int graph[V][V], int src)
{
    int distance[V]; //initializing output array

    bool sptSet[V]; // list of visited nodes

    // Initializing all distances as INFINITE and sptSet[] as false
    for (int i = 0; i < V; i++)
        distance[i] = INT_MAX, sptSet[i] = false;

    // Setting distance of source as 0
    distance[src] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < V - 1; count++) {

        //calling minDistance to pick next vertex
        int u = minDist(distance, sptSet);

        // Mark the picked vertex as visited
        sptSet[u] = true;

        //Relaxing all neighbours of U
        for (int v = 0; v < V; v++)
        {
            if (!sptSet[v] && graph[u][v] && distance[u] != INT_MAX
                && distance[u] + graph[u][v] < distance[v])
                distance[v] = distance[u] + graph[u][v];
    }

    // print the constructed distance array
    printSolution(distance);
}

// driver function
int main()
{

    //Example graph
    //Same as Graph in example diagram above

    int graph[V][V] = { {0,4,5,0,0,0},
                        {4,0,11,9,7,0},
                        {5,11,0,0,3,0},
                        {0,9,0,0,13,2},
                        {0,7,3,13,0,6},
                        {0,0,0,2,6,0}};
     int source=0;
     dijkstra(graph, source);

    return 0;
}

Output for Above Code

Vertex    Distance from Source
A         0
B         4    
C         5    
D         13
E         8
F         14

Explanation of C++ Code

• This is the explanation for the above C++ code.
• First let’s recall what all we require for Dijkstra's Algorithm.
  We need a graph and a source vertex.
• The graph and source are defined in the main function.
• First function we have is the minDist function. This function returns a vertex which has the smallest path and is also unvisited.
• Next we have is the printSolution function which prints the distance array.
• Then we have the dijkstra function. This is where most of the work is done. An array named distance has been created which stores the distance to each node from the source. Initially, all the values in the array are set to INT_MAX(it used to represent infinity) except the source which is set to zero.
• Then we have another array visited which stores whether a vertex has been visited or not. Initially we mark all the vertices as unvisited (represented here by false).
• Then a loop is run V times. In every iteration the minDist function is called to pick the unvisited node with the smallest path. The picked node is then marked visited.
• Then all the neighbours of the picked node are relaxed. This means that for each neighbour, we try to find a path to it using our currently picked node and if we find such a path that is also smaller than the node’s current path, the node’s path is updated to this newly found path.(distance[node]] is updated).
• This process is continued for all the nodes of the graph and finally the printSolution function is called to print the solution.

2. Implementation of Dijkstra Algorithm in JAVA

import java.util.*;
import java.lang.*;
import java.io.*;

class dijkstra_algo {
    //Function to find the vertex with minimum distance   
    static final int n = 6;//size of graph

    int min_dist(int distance[], Boolean visited[])
    {

        int min = Integer.MAX_VALUE, min_index = -1;

        for (int v = 0; v < n; v++)
            if (visited[v] == false && distance[v] <= min) {
                min = distance[v];
                min_index = v;
            }

        return min_index;
    }

    //Function to print the constructed distance array
    void printSolution(int distance[], int n)
    {
        System.out.println("Vertex      Distance from Source");
        for (int i = 0; i < n; i++)
            System.out.println(((char)(i+65)) + " \t\t \t" + distance[i]);
    }

    // Function that implements Dijkstra's algorithm

    void dijkstra(int graph[][], int source)
    {
        int distance[] = new int[n]; // The output array


        Boolean visited[] = new Boolean[n];

        // Initialize all distances as INFINITE and stpSet[] as false
        for (int i = 0; i < n; i++) {
            distance[i] = Integer.MAX_VALUE;//initializing infinity
            visited[i] = false;
        }

        // Distance of source vertex from itself is always 0
        distance[source] = 0;

        // Find shortest path for all vertices
        for (int count = 0; count < n - 1; count++) {
            // Pick the minimum distance vertex from unvisited vertices
            int u = min_dist(distance, visited);

            // Mark the picked vertex as visited
            visited[u] = true;

            // Updating dist value of the adjacent vertices of the
            // picked vertex.
            for (int v = 0; v < n; v++)

                //relaxing all the neighbouring vertices
                if (!visited[v] && graph[u][v] != 0 && 
                   distance[u] != Integer.MAX_VALUE && distance[u] + graph[u][v] < distance[v])
                    distance[v] = distance[u] + graph[u][v];
        }

        // print the constructed distance array
        printSolution(distance, n);
    }

    // Driver method
    public static void main(String[] args)
    {

        int graph[][] = new int[][] { {0,4,5,0,0,0},
                                      {4,0,11,9,7,0},
                                      {5,11,0,0,3,0},
                                      {0,9,0,0,13,2},
                                      {0,7,3,13,0,6},
                                      {0,0,0,2,6,0}};
        dijkstra_algo t = new dijkstra_algo();
        int src=0;
        t.dijkstra(graph, src);
    }
}

Output for Above Code

Vertex    Distance from Source
A         0
B         4    
C         5    
D         13
E         8
F         14

3. Implemetation of Dijkstra Algorithm in Python

# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX
#import sys
intmax=9999999999 
class Graph():

    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)]
                    for row in range(vertices)]



    def printSolution(self, dist):
        print ("Vertex \tDistance from Source")
        for node in range(self.V):
            print (node, "\t", dist[node])

    # A utility function to find the vertex with
    # minimum distance value, from the set of vertices
    # not yet included in shortest path tree
    def minDistance(self, dist, sptSet):

        # Initialize minimum distance for next node
        min = intmax

        # Search not nearest vertex not in the
        # shortest path tree
        for u in range(self.V):
            if dist[u] < min and sptSet[u] == False:
                min = dist[u]
                min_index = u

        return min_index

    # Function that implements Dijkstra's single source
    # shortest path algorithm for a graph represented
    # using adjacency matrix representation
    def dijkstra(self, src):

        dist = [intmax] * self.V
        dist[src] = 0
        sptSet = [False] * self.V

        for cout in range(self.V):

            # Pick the minimum distance vertex from
            # the set of vertices not yet processed.
            # x is always equal to src in first iteration
            x = self.minDistance(dist, sptSet)

            # Put the minimum distance vertex in the
            # shortest path tree
            sptSet[x] = True

            # Update dist value of the adjacent vertices
            # of the picked vertex only if the current
            # distance is greater than new distance and
            # the vertex in not in the shortest path tree
            for y in range(self.V):
                if self.graph[x][y] > 0 and sptSet[y] == False and dist[x]!=intmax and dist[y] > dist[x] + self.graph[x][y]:
                        dist[y] = dist[x] + self.graph[x][y]

        self.printSolution(dist)

# Driver program
g = Graph(6)
g.graph = [[0,4,5,0,0,0],
        [4,0,11,9,7,0],
        [5,11,0,0,3,0],
        [0,9,0,0,13,2],
        [0,7,3,13,0,6],
        [0,0,0,2,6,0],
        ];

g.dijkstra(0);

Output for Above Code

Vertex    Distance from Source
A         0
B         4    
C         5    
D         13
E         8
F         14

Dijkstra Algorithm Time Complexity

Complexity analysis for dijkstra's algorithm with adjacency matrix representation of graph.

Time complexity of Dijkstra's algorithm is $O(V^2)$ where V is the number of verices in the graph.

It can be explained as below:

1. First thing we need to do is find the unvisited vertex with the smallest path. For that we require $O(V)$ time as we need check all the vertices.
2. Now for each vertex selected as above, we need to relax its neighbours which means to update each neighbours path to the smaller value between its current path or to the newly found. The time required to relax one neighbour comes out to be of order of O(1) (constant time).
3. For each vertex we need to relax all of its neighbours, and a vertex can have at most V-1 neighbours, so the time required to update all neighbours of a vertex comes out to be [O(V) * O(1)] = O(V)

So now following the above conditions, we get:

Time for visiting all vertices =O(V)

Time required for processing one vertex=O(V)

Time required for visiting and processing all the vertices

$$ = O(V)*O(V) =O(V^2) $$

So the time complexity of dijkstra's algorithm using adjacency matrix representation comes out to be $O(V^2)$

Space complexity of adajacency matrix representation of graph in the algorithm is also $O(V^2)$ as a V*V matrix is required to store the representation of the graph. An additional array of V length will also be used by the algortihm to maintain the states of each vertex but the total space complexity will remain O$(V^2)$.

The time complexity of dijkstra’s algorithm can be reduced to O((V+E)logV) using adjacency list representation of the graph and a min-heap to store the unvisited vertices, where E is the number of edges in the graph and V is the number of vertices in the graph.

With this implementation, the time to visit each vertex becomes O(V+E) and the time required to process all the neighbours of a vertex becomes O(logV).

Time for visiting all vertices =O(V+E)

Time required for processing one vertex=O(logV)

Time required for visiting and processing all the vertices

$$ = O(V+E)*O(logV) = O((V+E)logV) $$

The space complexity in this case will also improve to O(V) as both the adjacency list and min-heap require O(V) space. So the total space complexity becomes

$$ O(V)+O(V)=O(2V) = O(V) $$

Proof of Correctness

The main assertion on which Dijkstra's algorithm correctness is based is the following:

After any vertex v becomes marked, the current distance to it d[v] is the shortest, and will no longer change.

Let assume

• dijkstra(s,t) to be the shortest distance between two nodes s and t as calculated by dijksta’s algorithm
• shortest(s,t) to be the actual shortest distance between two nodes s and t.

Now our proposition is:

dijkstra(s,t)=shortest(s,t) for a vertex t that has been visited

Now we will prove this proposition by contradiction.

So let’s assume that our above proposition is false.

dijkstra(s,t)>shortest(s,t) for a vertex t that has been visited

Now assume vertex x to be the first visited vertex for which dijkstra(s,x)>shortest(s,x), so for all vertices z upto before x, dijkstra(s,z)>shortest(s,z)

Now assume vertex y to be a visited vertex on the real shortest path from source to x, and vertex z to be an unvisited vertex on the real shortest path from source to x.

We can conclude that:

dijkstra(s,y) = shortest(s,y) 

dijkstra(s,z) = dijkstra(s,y)+edgecost(y,z)

dijkstra(s,x) < dijkstra(s,z) as `x` is visited before `z`.

But, sub path of a shortest path is also a shortest path which implies

shortest(s,x)=shortest(s,z)+shortest(z,x)

We can now conclude that:

 dijkstra(s,x) < dijkstra(s,z)
 dijkstra(s,x) < dijkstra(s,y)+edgecost(y,z)
 dijkstra(s,x) = shortest(s,y)+edgecost(y,z)+shortest(z,x)
 dijkstra(s,x) = shortest(s,x)

This result is contradictory to our proposition
dijkstra(s,t)>shortest(s,t)

So the statemant that the condition dijkstra(s,t)=shortest(s,t) is false is false, our statement dijkstra(s,t)=shortest(s,t) is true.

Hence we have proved that the dijkstra’s algorithm path will be the shortest path to any vertex.

Applications of Dijkstra Algorithm

Dijkstra's algorithm has many applications:

1. Digital Mapping Services like Google Maps: Suppose you want to travel from one city to another city. You use Google maps to find the shortest route. How will it work? Assume the city you are in to be the source vertex and your destination to be another vertex. There will still be many cities between your destination and starting point. Assume those cities to be intermediate vertices. The distance and traffic between any two cities can be assumed to be the weight between each pair of verices. Google maps will apply dijkstra algorithm on the city graph and find the shortest path.
2. Designate Servers: In a network, Dijkstra's Algorithm can be used to find the shortest path to a server for transmitting files amongst the nodes on a network.
3. IP Routing: Dijkstra's Algorithm can be used by link state routing protocols to find the best path to route data between routers.

Join our Data Structures in C++ Course now and gain a competitive edge in your programming career!

Conclusion

1. In this article firstly we have understood the basic working of Dijkstra's algorithm.
2. After that we came to an example to better understand the working of dijkstra's algorithm.
3. Then we have also studied how to write code for dijkstra's algorithm with the help of psuedocode.
4. After that we have also implemented dijkstra's algorithm in C++ with explanation and have also implemented it in JAVA and Python.
5. That is followed by a time complexity analysis of dijkstra's algorithm.
6. Finally we have proved the correctness of dijkstra's algorithm mathematically and have also discussed applications of dijkstra’s algorithm.

See More

• Dijkstra Algorithm Python
• Dijkstra’s Algorithm Java