The Shortest Path - Dijkstra Algorithm: A detailed Overview
Updated on Mar 07, 2025 | 19 min read | 3.5k views
Share:
For working professionals
For fresh graduates
More
Updated on Mar 07, 2025 | 19 min read | 3.5k views
Share:
Table of Contents
The Dutch computer scientist Edsger Dijkstra in 1959, spoke about the shortest path algorithm that could be applied to a weighted graph. This graph can be of two types – directed or undirected. A precondition of the graph is that there should be a non-negative value on its very edge. Edsger named this algorithm ‘Dijkstra’s Algorithm’.
This blog will explore the concept of the dijkstra algorithm and ways to implement it in various programming languages.
Graphs are non-linear data structures depicting the connections between elements known as vertices or nodes. The arcs or lines forming the connection between two nodes in a graph are termed edges. Simply put, a graph comprises a set of Edges (E) and vertices (V). This graph can be denoted G (V, E). Two graph nodes connect only when an edge exists between them.
Graphs can be broadly classified into directed and undirected graphs.
These graphs consist of edges with direction. The edges denote a one-way relationship in such graphs where a single direction traverses each edge. The figure above shows a simple directed graph consisting of five edges and four nodes. Arrows are used in place of simple lines to denote directed edges.
Graphs with an edge but no fixed direction are known as undirected graphs. In these graphs, the edge denotes a two-way relationship where we can communicate in both directions. The figure above shows a simple undirected graph comprising six edges and six nodes. Learn more about this topic in our detailed blog post
Weighted graphs are those where each edge is assigned a ‘weight’ or ‘cost.’ This weight can represent time, distance or anything representing the connection between the nodes or vertices it links. Dijkstra’s Algorithm considers these weights as essential elements.
The image above shows the weighted graph with a number beside each edge, signifying the weight of the corresponding edge.
Alternately called single source shortest path algorithm, Dijkstra’s Algorithm is used to figure out the shortest path in weighted graphs or the shortest distance between the starting node and target node in weighted graphs. It uses the weights of the edges to find the route that minimises the total weight or distance between the starting node and the other nodes.
This algorithmic process provides the shortest distance from a precise source node to all other nodes inside a graph. This differs from the minimum spanning tree since the shortest path between two nodes might not include all the graph nodes.
Dijkstra’s Algorithm is used in GPS devices to find the shortest path between your current location and your destination. Additionally, Dijkstra’s Algorithm in computer networks is used for routing protocols.
Look at some of the important features of the algorithm before moving on to Dijkstra’s Algorithm steps for implementing the algorithm.
Let’s move on to the step-by-step process of implementing Dijkstra’s Algorithm.
For a better understanding, consider the illustration below to explain Dijkstra’s Algorithm with examples.
Now that we have a fair grasp of Dijkstra Algorithm example, let’s dive into the pseudocode for Dijkstra Algorithm.
Now look at this pseudocode of the above example.
Pseudocode:
function Dijkstra Algorithm(Graph, source node)
// iterating through the nodes in Graph and set their distances to INFINITY
for each node N in Graph:
distance[N] = INFINITY
previous N = NULL
If N != source_node, add N to Priority Queue G // setting the distance of the source node of the Graph to 0
distance source_node]=0
// iterating until the Priority Queue G is not empty
while G is NOT empty:
// selecting a node Q having the least distance and marking it as visited
Q = node in G with the least distance
mark Q visited
// iterating through the unvisited neighbouring nodes of the node Q and performing
relaxation accordingly
for each unvisited neighbour node N of Q
temporary distance = distance[Q] + distance between(Q, N)
if the temporary distance is less than the given distance of the path to the Node.
updating the resultant distance with the minimum value
if temporary distance < distance[N]
distance[N]:= temporary distance
previousNO
//returning the final list of distance
return distance[], previous[]
In the pseudocode above, a function is built with two parameters — the source node and the Graph made up of the nodes. In this function, each node in the Graph has been iterated through their initial distance set to INFINITY, and the previous node value set to NULL. Additionally, before adding each node to the priority queue, it was checked to confirm it was not a source node.
The source node’s length is set to 0. After going through each node in the priority queue once, the closest one is chosen and marked as visited. It is repeated through the selected node’s unexplored neighbours and relaxed wherever necessary.
Finally, the original and temporary distances between the source and destination nodes are compared and updated with the resulting distance with the minimum value and the prior node information. For the last step, we returned the final list of distances with the prior node information.
Check out our free technology courses to get an edge over the competition.
This section will describe the implementation of the algorithm in various programming languages.
Use the following code to implement Dijkstra Algorithm in C.
File: DijkstraAlgorithm.c
// Implementation of Dijkstra's Algorithm in C
// importing the standard I/O header file
#include <stdio.h>
// defining some constants
#define INF 9999
#define MAX 10
// prototyping of the function
void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start);
// defining the function for Dijkstra's Algorithm
void DijkstraAlgorithm(int Graph[MAX][MAX], int size, int start) {
int cost[MAX][MAX], distance[MAX], previous[MAX];
int visited_nodes[MAX], counter, minimum_distance, next_node, i, JE
// creating cost matrix
for (i = 0; i < size; i++)
for (j = 0; j < size; j++)
if (Graphi [i][j] == 0)
cost[i][j] = INF;
else
cost[i][j]= Graphjn:[i][j];
for (i = 0; i < size; i++) {
distance[i] = cost[start][i];
previous[i] = start;
visited_nodes[i] = 0;
}
distance[start] = 0;
visited_nodes[start] = 1;
counter = 1;
while (counter < size - 1) {
minimum distance = INF;
for (i = 0; i < size; i++)
if (distance[i] < minimum_distance && !visited_nodes[j]) {
minimum distance = distance[i];
next_node = i;
}
visited_nodes[next_node] =1;
for (i = 0; i < size; i++)
if (!visited_nodes[i])
if (minimum_distance + cost[next_node][i] < distance[i]) {
distance[i] = minimum_distance + cost[next_node][i];
previous[i] = next_node;
}
counter++;
}
// printing the distance
for (i=0; i< size; i++)
if (i != start) {
printf("\nDistance from the Source Node to %d: %d", i, distance[i]);
}
}
// main function
int main(){
// defining variables
int Graph[MAX][MAX], i, j, size, source;
// declaring the size of the matrix
size = 7;
// declaring the nodes of graph
Graph[0][0] = 0;
Graph[0][1] = 4;
Graph[0][2] = 0;
Graph[0][3] = 0;
Graph[0][4] = 0;
Graph[0][5] = 8;
Graph[0][6] = 0;
Graph[1][0] = 4;
Graph[1][1] <= 0;
Graph[1][2] = 8:
Graph[1][3] = 0:
Graph[1][4] = 0;
Graph[1][5] = 11;
Graph[1][6] = 0;
Graph[2][0] = 0;
Graph[2][1] = 8:
Graph[2][2] <= 0;
Graph[2][3] = 7:
Graph[2][4] = 0;
Graph [2][5] = 4;
Graph[2][6] = 0;
Graph[3][0] = 0;
Graph [3][1] = 0;
Graph[3][2] <= 7
Graph[3][3] <=0
Graph[3][4] = 9,
Graph[3]][5] = 14;
Graph[3][6]= 0;
Graph [4][0] = 0;
Graph [4][1] = 0;
Graph[4][2] = 0;
Graph[4][3]= 9;
Graph[4][4] = 0;
Graph[4][5] = 10;
Graph[4][6] = 2:
Graph[5][0] = 0;
Graph[5][1] = 0;
Graph[5][2] = 4;
Graph [5][3] = 14
Graph [5][4] = 10;
Graph [5][5]= 0;
Graph[5][6]= 2;
Graph[6][0] = 0;
Graph[6][1]=0;
Graph[6][2] = 0;
Graph[6][3] = 0;
Graph[6][4] = 2;
Graph[8][5] = 0;
Graph[8][6] = 1;
source= 0;
//calling the DijkstraAlgorithm() function by passing the Graph, the number of nodes and
the source node
Dijkstra Algorithm(Graph, size, source);
return 0;
}
Use the following code to implement Dijkstra’s Algorithm in C++.
File: DijkstraAlgorithm.cpp
// Implementation of Dijkstra's Algorithm in C++
// importing the required header files
#include <iostream>
#include <vector>
// defining constant
#define MAX_INT 10000000
// using the standard namespace
using namespace std;
// prototyping of the DijkstraAlgorithm() function
void DijkstraAlgorithm();
// main function
int main(){
DijkstraAlgorithm();
return 0;
}
// declaring the classes
class Vertex;
class Edge;
// prototyping the functions
void Dijkstra();
vector<Vertex*>* Adjacent Remaining Nodes(Vertex" vertex);
Vertex Extract_Smallest(vector<Vertex*>& vertices);
int Distance(Vertex vertexOne, Vertex* vertexTwo);
bool Contains(vector<Vertex">& vertices, Vertex vertex);
vold Print Shortest Route To(Vertex" des);
// instantiating the classes
vector<Vertex"> vertices;
vector<Edge"> edges;
// defining the class for the vertices of the graph
class Vertex{
public:
Vertex(char id)
: id(id), prev(NULL), distance_from_start(MAX_INT) {
vertices.push_back(this);
}
public:
char id;
Vertex* prev;
int distance_from_start;
};
// defining the class for the edges of the graph
class Edge {
public:
Edge(Vertex* vertexOne, Vertex vertexTwo, int distance)
: vertexOne(vertexOne), vertexTwo(vertexTwo), distance(distance) {
edges.push_back(this);
}
bool Connects(Vertex* vertexOne, Vertex vertexTwo) {
return(
(vertexOne == this->vertexOne &&
vertex Two == this->vertexTwo) ||
(vertexOne == this->vertexTwo &&
vertexTwo == this->vertexOne));
}
public:
Vertex vertexOne:
Vertex vertexTwo:
int distance;
};
// defining the function to collect the details of the graph
void DijkstraAlgorithm() {
// declaring some vertices
Vertex vertex_a= new Vertex('A');
Vertex vertex_b = new Vertex('B');
Vertex vertex_c = new Vertex('C');
Vertex vertex_d = new Vertex('D');
Vertex vertex_e = new Vertex('E');
Vertex vertex_f = new Vertex('F');
Vertex vertex_g = new Vertex('G');
// declaring some edges
Edge* edge_1 = new Edge(vertex a, vertex_c, 1);
Edge* edge_2 = new Edge(vertex a, vertex_d, 2);
Edge* edge_3 = new Edge(vertex b, vertex_c, 2);
Edge* edge_4 = new Edge(vertex c, vertex_d, 1):
Edge* edge_5 = new Edge(vertex b, vertex_f, 3);
Edge* edge_6 = new Edge(vertex c, vertex_e, 3);
Edge* edge_7 = new Edge(vertex e, vertex_f, 2);
Edge* edge_8 = new Edge(vertex d, vertex_g, 1);
Edge* edge_9= new Edge(vertex g, vertex_f, 1);
vertex a distance from start = 0; // setting a start vertex
// calling the Dijkstra() function to find the shortest route possible
Dijkstra();
//calling the prient_shortest_route_to() function to print the shortest route from the
Source vertex to the destination vertex
Print_shortest_Route_To(vertex_f);
// defining the function for Dijkstra's Algorithmn
void Dijkstra(){
while (vertices.size() > 0) {
Vertex smallest = Extract Smallest(vertices);
vector<Vertex adjacent nodes =
Adjacent_Remaining_Nodes(smallest);
const int size = adjacent_nodes -> size();
for (int i = 0; i < size; ++i) {
Vertex adjacent = adjacent nodes → at);
int distance = Distance(smallest, adjacent) +
smallest -> distance_from_start;
if (distance < adjacent -> distance_from_start) {
adjacent->distance from start = distance:
adjacent -> prev = smallest;
}
}
delete adjacent_nodes;
}
}
// defining the function to find the vertex with the shortest distance, removing it, and
returning it
Vertex* Extract Smallest(vector<Vertex">& vertices) int size = vertices.size();
if (size == 0) return NULL;
int smallest_position = 0;
Vertex* smallest = vertices.at(0);
for (int i = 1; i < size; ++i) {
Vertex* current = vertices.at(i);
if (current ->distance_from_start <
smallest -> distance_from_start)
smallest=current;
smallest_position=i;
}
}
vertices.erase(vertices.begin() + smallest_position);
return smallest;
}
// defining the function to return all vertices adjacent to 'vertex' which are still in the
vertices collection.
vector<Vertex*>* Adjacent Remaining Nodes(Vertex" vertex) {
vector<Vertex"> adjacent nodes = new vector<Vertex">();
const int size = edges.size();
for (int i = 0; i < size; ++i) {
Edge* edge = edges.at(i);
Vertex adjacent = NULL;
if (edge -> vertexOne == vertex) {
adjacent = edge >> vertexTwo;
}else if (edge -> vertexTwo == vertex) {
adjacent = edge-> vertexOne;
}
if (adjacent && Contains(vertices, adjacent)) {
adjacent nodes -> push_back(adjacent);
}
}
return adjacent nodes;
}
// defining the function to return distance between two connected vertices
int Distance(Vertex* vertexOne, Vertex* vertexTwo) {
const int size = edges.size();
for (int i = 0; i < size; ++i) {
Edge* edge = edges.at(i);
if (edge -> Connects(vertexOne, vertexTwo)) {
return edge -> distance;
}
}
return -1; // should never happen
}
// defining the function to check if the 'vertices' vector contains 'vertex'
bool Contains(vector<Vertex*>& vertices, Vertex* vertex) {
const int size = vertices.size();
for (int i = 0; i < size; ++i) {
if (vertex == vertices.at(i)) {}
return true;
}
}
return false;
}
// defining the function to print the shortest route to the destination
vold Print_Shortest_Route _To(Vertex* des) {
Vertex" prev = des;
cout << "Distance from start: "
<< des -> distance_from_start << endl;
while (prev) {
cout << prev -> id <<"";
prev = prev-> prev;
}
cout << endl;
}
Use the following code to implement Dijkstra’s Algorithm in Java programming language.
File: DijkstraAlgorithm.java
// Implementation of Dijkstra's Algorithm in Java
// defining the public class for Dijkstra's Algorithm
public class DijkstraAlgorithm {
// defining the method to implement Dijkstra's Algorithm
public void dijkstraAlgorithm(int[][] graph, int source) {
// number of nodes
int nodes = graph.length;
boolean[] visited_vertex = new boolean[nodes];
int[] dist = new int[nodes];
for (int i=0; i<nodes; i++){
visited_vertex] = false;
dist[i] = Integer.MAX_VALUE;
}
// Distance of self loop is zero
dist[source] = 0;
for (int i=0; i<nodes, i++) {
//Updating the distance between neighbouring vertex and source vertex
int u= find_min_distance(dist, visited vertex);
visited_vertex[u] = true;
// Updating the distances of all the neighbouring vertices
for (int v=0; y < nodes: v++) {
if (visited vertex(v) && graph[u][v]! = 0 && (dist[u] + graph[u][v] < dist{v})) {
dist[v] = dist[u] + graph[u][v];
}
}
}
for (int i=0; i < dist.length; i++) {
System.out.println(String format("Distance from Vertex %s to Vertex %s is %s",
source, i, dist[i]));
}
}
//definding the medhod to find the minimum distance
privae static int find_min_distance(int[]dist, boolean[] visited_vertex) {
int minimum_distance = integer.Max_value;
int mininum_distance_vertex =-1;
for (int i=0; i<dist. length; i++){
if (visited vertex) && dist[i] < minimum_distance) {
minimum_distance = dist[i]}
minimum distance vertex=i;
}
}
retum minimum_distance_vertex;
}
// main function
public static void main(String[] args) {
// declaring the nodes of the graphs
int graph[][] = new int[][]{
{0,1,1,2,0,0,0},
{0,0,2,0,0,3,0},
{1,2,0,1,3,0,0},
{2,0,1,0,2,0,1},
{0,0,3,0,0,2,0},
{0,3,0,0,2,0,1},
{0,2,0,1,0,1,0}
};
//instantiating the DijkstraAlgorithm() class
DijkstraAlgorithm Test = new DijkstraAlgorithm())
// calling the dijkstraAlgorithm() method to find the shortest distance from the source
node to the destination node
Test.dijkstraAlgorithm(graph, 0)
}
}
Use the following code to implement Dijkstra’s Algorithm in Python.
File: DikstraAlgorithm.py
#Implementation of Dijkstra's Algorithm in Python
#importing the sys module
import sys
#declaring the list of nodes for the graph
nodes=[
[ 0, 0, 1, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 1, 0],
[1, 1, 0, 1, 1, 0, 0
[1, 0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1, 0]
[0, 1, 0, 0, 1, 0, 1, ]
[ 0, 0, 0, 1, 0, 1, 0]
]
#declaring the list of edges for the graph
edges = [
[0,0,1,0,2,0,0],
[0, 0, 2, 0, 0, 3, 0],
[1,2,0,1,3,0,0],
[2, 0, 1, 0, 0, 0, 1],
[0,0,3,0,0,2, 0],
[0, 3, 0, 0, 2, 0, 1],
[0, 0, 0, 1, 0, 1,0]
]
# declaring the list of edges for the graph
edges=[
[ 0, 0, 1, 0, 2, 0, 0],
[ 0, 0, 2, 0, 0, 3, 0],
[ 1, 2, 0, 1, 3, 0, 0],
( 2, 0, 1, 0, 0, 0, 1, 1],
[ 0, 0, 3, 0, 0, 2, 0],
[0, 3, 0, 0, 2, 0, 1],
[ 0, 0, 0, 1, 0, 1, 0],
]
#defining the function to find which node is to be visited next
def toBevisited():
global visitedAndDistance
V=-10
for index in range(numberOfNodes);
If visitedAndDistance[index][0] == 0 and (v <0 or visitedAndDistance index][1]<=
visitedAndDistance[v][1]):
v=index
return v
#finding the number of nodes in the graph
numberOfNodes = len(nodes[0])
visitedAndDistance = [[0, 0]
for i in range(numberOfNodes - 1):
visitedAndDistance.append([0, sys.maxsize])
for node in range(numberOfNodes):
#finding the next node to be visited
toVisit = toBeVisited()
for neighborIndex in range(numberOfNodes)
#updating the new distances
if nodes to Visit][neighborIndex]== 1 and visitedAndDistance(neighborinbox[[0] ==0:
newDistance = visitedAndDistance toVisit][1] + edges[toVisit][neighborindex]
if visitedAndDistance neighborfndex][1] > newDistance:
visitedAndDistance[neighborIndex][1] = newDistance
visitedAndDistance(toVisit [0] =1
i=0
#printing the distance
for distance in visitedAndDistance:
print("Distance of", chr(ord("A") + i), "from source node", distance[1])
i=i+1
Mentioned below are some Dijkstra’s Algorithm examples and their real-world applications.
Every transmission line in a mobile network consists of a bandwidth, ‘B’. The transmission line’s highest supported frequency is known as the bandwidth. In general, a line reduces a signal if the signal frequency is higher in that line. The amount of data transmitted over a line is measured as bandwidth.
Let’s imagine a city as a graph, where the graph nodes represent the switching station and the edges represent the transmission lines. The weight of the edges represents the bandwidth, or ‘B’. As a result, the mobile network can also be considered a type of shortest-distance problem that can be resolved using Dijkstra’s Algorithm.
We often try to find the distance between two cities interlinked with many routes or paths. We resort to Google Maps to show us the minimal distance. This is only possible because Dijkstra’s Algorithm aids the application in determining which portion of the path is shortest between two specified places.
Consider India as a network, with the cities and locations acting as the nodes and the routes connecting them as the edges. It is possible to figure out the shortest paths between any two cities or locations using Dijkstra’s Algorithm.
Let’s consider that a person needs software to create a customer flight schedule. A database containing all flights and airports is available to the agent. The flights also consist of departure and arrival timings in addition to the origin airport, flight number and destination. Here, the agents can apply Dijkstra’s Algorithm to compute the earliest arrival time for the chosen destination from the original airport and the specified start time.
Dijkstra’s Algorithm comes with its own set of advantages and disadvantages.
Check Out upGrad’s Software Development Courses to upskill yourself.
The Dijkstra Algorithm is useful for finding the shortest path between a source node and all other nodes in a graph. An in-depth knowledge of this algorithm is crucial for data scientists, along with the know-how to implement it in various programming languages. Enroll in an online data science course to understand it in detail and learn more about Dijkstra’s shortest path algorithm example and its real-world applications.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
India’s #1 Tech University
Executive PG Certification in AI-Powered Full Stack Development
77%
seats filled
Top Resources