What Is Dijkstra Algorithm Shortest Path Algorithm: Explained with Examples
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 Dijkstra’s shortest path algorithm and ways to implement it in various programming languages.
Understanding Graphs
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.
Graph components
- Edges – Edges, also called arcs, are lines connecting two vertices or graph nodes. These are.
- Vertices – Basic graph elements, also known as nodes, vertices depict real-life people and objects.
Graph Types
Graphs can be broadly classified into directed and undirected graphs.
1. Directed Graph
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.
2. Undirected Graphs
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 Graph
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.
Introduction to Dijkstra’s Algorithm
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.
Why Do We Use Dijkstra’s Algorithm?
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.
A Step-by-Step Guide to Implementing Dijkstra’s Algorithm
Look at some of the important features of the algorithm before moving on to Dijkstra’s Algorithm steps for implementing the algorithm.
- Dijkstra’s Algorithm starts from the source node. The algorithm examines the whole graph to find the shortest path between that node and all other nodes.
- It keeps track of the presently recognised shortest path from each node to the starting node. It updates the values if it can find a different shortest path.
- After the algorithm has found the shortest distance from the source node to another node, it marks the node as ‘visited’ and adds it to the path.
- This process continues until the path contains all nodes in the graph. With the help of this, a path is created connecting the source node to all other nodes. This path is created following the probable shortest distance to reach each node.
Let’s move on to the step-by-step process of implementing Dijkstra’s Algorithm.
- Mark all vertices as unvisited.
- Mark the source node with a present distance of 0 while marking the other nodes as infinity.
- Fix the source node as the current node.
- Analyse all the unvisited neighbours of the current node and calculate their distances. Add the present distance of the current node to the edge’s (connecting current node and neighbour node) weight to calculate the distance.
- Compare the most recent distance to the distance already assigned to the neighbouring node, then set that distance as the new current distance for that node.
- Consider all the current node’s unvisited neighbours after that and mark the current node as visited.
- An algorithm has ended if the destination node has been marked as visited.
- If not, select the unvisited node marked with the smallest distance and fix it as the latest current node. Repeat the process once more from step 4.
Dijkstra’s Shortest Path Algorithm Example
For a better understanding, consider the illustration below to explain Dijkstra’s Algorithm with examples.
- Begin with a weighted graph.
- Select a source node and mark it as 0. Assign infinity to the other nodes.
- Move to each node and update the path distance.
- If the path distance of the adjacent node is smaller than the new path distance, it is unnecessary to update it.
- You must avoid updating the path distances of nodes you have visited.
- We choose the unvisited node with the smallest path distance after each iteration. That is why choose 5 before 7.
- You may notice how the rightmost node gets its path distance updated twice.
- Repeat the steps until all the nodes have been visited.
Understanding Pseudocode for Dijkstra’s Algorithm
Now that we have a fair grasp of Dijkstra Algorithm example, let’s dive into the pseudocode for Dijkstra Algorithm.
- Keep a record of the path length of every vertex. Keep each vertex’s path length inside an array with size n, where n is the total number of vertices.
- Find the shortest path and the distance of that path. To overcome this issue, map each vertex to the vertex that last updated its path distance.
- After completing the algorithm, try backtracking the destination vertex to the source vertex to find the path.
- Use a minimum Priority Queue to find the vertex with the smallest path length efficiently.
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.
Using Dijkstra’s Algorithm in Various Programming Languages
This section will describe the implementation of the algorithm in various programming languages.
Dijkstra’s Algorithm C Code
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; }
Read our Popular Articles related to Software Development
| Why Learn to Code? How Learn to Code? | How to Install Specific Version of NPM Package? | Types of Inheritance in C++ What Should You Know? |
Dijkstra Algorithm C++ Code
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;
}
Dijkstra Algorithm Java Code
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)
}
}
Dijkstra Algorithm Python Code
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
In-Demand Software Development Skills
Real-life Applications of Dijkstra’s Algorithm
Mentioned below are some real-world applications of Dijkstra’s Algorithm.
Mobile Network
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.
Google Maps
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.
Flight Programme
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.
Pros and Cons of Dijkstra’s Algorithm
Dijkstra’s Algorithm comes with its own set of advantages and disadvantages.
Advantages
- Dijkstra’s Algorithm has a nearly linear space and time complexity.
- It can only be used with directed weighted graphs. This graph’s edges must be non-negative.
- Calculating the shortest distance from a single node to all other nodes is possible by using Dijkstra’s Algorithm. It is also possible to measure the shortest path from a source node to a destination node by ending the algorithm after we reach the shortest path for the destination node.
Disadvantages
- Dijkstra’s Algorithm cannot handle negative edges.
- This algorithm performs an obscured exploration. This takes up too much time during processing.
- Maintenance is required to keep track of the visited nodes.
- This algorithm cannot measure the exact shortest distance since it enters the acyclic graph.
Check Out upGrad’s Software Development Courses to upskill yourself.
Conclusion
Dijkstra’s 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. Enrol 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.
![Ethical Hacker Salary India in 2024 [Freshers and Experienced]](/__khugblog-next/image/?url=https%3A%2F%2Fd14b9ctw0m6fid.cloudfront.net%2Fugblog%2Fwp-content%2Fuploads%2F2021%2F03%2F1982_.png&w=3840&q=75)
![6 Exciting Cyber Security Project Ideas & Topics For Freshers & Experienced [2024]](/__khugblog-next/image/?url=https%3A%2F%2Fd14b9ctw0m6fid.cloudfront.net%2Fugblog%2Fwp-content%2Fuploads%2F2020%2F10%2F1312.png&w=3840&q=75)
![Cyber Security Salary in India: For Freshers & Experienced [2024]](/__khugblog-next/image/?url=https%3A%2F%2Fd14b9ctw0m6fid.cloudfront.net%2Fugblog%2Fwp-content%2Fuploads%2F2021%2F01%2F1351.png&w=3840&q=75)
