`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:**

- Greedy Algorithm
- 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

- Mark the source node with a current distance of
`0`

and the rest with infinity. - Set the non-visited node with the smallest current distance as the current node, lets say
`C`

. - 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`

. - Mark the current node
`C`

as visited. - 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:

- 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. - 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). - 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:

**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.**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.**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

- In this article firstly we have understood the basic working of
`Dijkstra's algorithm`

. - After that we came to an example to better understand the working of
`dijkstra's algorithm`

. - Then we have also studied how to write code for
`dijkstra's algorithm`

with the help of psuedocode. - After that we have also implemented
`dijkstra's algorithm`

in C++ with explanation and have also implemented it in JAVA and Python. - That is followed by a time complexity analysis of
`dijkstra's algorithm`

. - Finally we have proved the correctness of
`dijkstra's algorithm`

mathematically and have also discussed applications of dijkstra’s algorithm.