Data Structure and Algorithm
SingleSource Shortest Paths Algorithm  Dijkstra's Algorithm
 Dijkstra’s Algorithm
 Working Principle of Dijkstra
 Dijkstra Implementation in C++
 Algorithm Explanation
 Time Complexity of Dijkstra’s Algorithm
 Space Complexity of Dijkstra’s Algorithm
 Applications of Dijkstra’s Algorithm
 Run C Programming Online Compiler
Consider you’re at home and want to navigate to a nearby restaurant. Almost instantaneously, your GPS system provides you with the fastest route to your dinner! Your GPS system uses Dijkstra's algorithm
as core algorithm to calculate the shortest path from your home to the restaurant. The GPS system represents locations (like your home, and restaurant) as nodes and the roads connecting these locations as edges. The distances or travel times along these roads are the weights.
Dijkstra’s algorithm has numerous realworld applications, such as finding the shortest paths in Google Maps and network routing.
¶Dijkstra’s Algorithm
Dijkstra’s algorithm is a pathfinding algorithm. It’s a simple yet powerful algorithm used to find the shortest paths between nodes in a graph when path cost is nonnegative. Imagine you’re at point A and you want to get to point B. There are multiple routes you can take, some longer than others. Dijkstra’s algorithm works by visiting each of these routes, and updating the paths by the shortest one it has found so far. It is also called the SingleSource Shortest Paths Algorithm since it finds all the shortest paths starting from a single node.
Here, suppose our destination is node 7
from node 1
. Among the potential shortest paths, we highlight the one with a total cost of 10, marked by redcolored edges. We initially journey from node 1
to node 2
, incurring a cost of 7. Continuing, we advance to node 5
, resulting in a total cost of 8. Progressing further to node 4
, our cumulative cost increases to 9, until finally arriving at node 7
with a concluding cost of 10.
¶Working Principle of Dijkstra
The algorithm works in few steps sequentially,

Initialization: The algorithm starts at the node where the journey begins (the source node) and sets the distance to zero. It sets the initial distance for all other nodes as infinity, indicating that we don’t yet know the shortest path to these nodes.

Visiting Nodes: The algorithm visits each node, starting with the one with the shortest known distance from the source. It calculates the distance from the source to each of its neighboring nodes and updates their distances if it finds a shorter path.

Updating Distances: The algorithm then moves to the next node with the shortest known distance and repeats the process, updating distances as it goes. This continues until it has visited all nodes and found the shortest path to each one.

Finding the Shortest Path: Once all the nodes have been visited, the algorithm has found the shortest path from the source to each node. To find the shortest path to a specific destination, it traces back through the nodes from the destination to the source, following the path with the shortest distances.
¶Dijkstra Implementation in C++
#include <iostream>
#include <vector>
#include <set>
#include <limits>
using namespace std;
// Define the adjacency list type for convenience
typedef vector<vector<pair<int, int>>> AdjacencyList;
// Dijkstra's algorithm using a set
vector<int> dijkstra(const AdjacencyList& graph, int start) {
int n = graph.size();
vector<int> dist(n, numeric_limits<int>::max()); // Distance from start to each node
dist[start] = 0;
set<pair<int, int>> activeVertices; // Set to manage nodes
activeVertices.insert({0, start});
while (!activeVertices.empty()) {
int where = activeVertices.begin()>second;
activeVertices.erase(activeVertices.begin());
for (auto edge : graph[where]) {
if (dist[edge.first] > dist[where] + edge.second) {
activeVertices.erase({dist[edge.first], edge.first});
dist[edge.first] = dist[where] + edge.second;
activeVertices.insert({dist[edge.first], edge.first});
}
}
}
return dist;
}
int main() {
int nodes = 7, edges = 10;
AdjacencyList graph(nodes + 1); // +1 to handle 1based indexing
// Hardcoded input
vector<vector<int>> input = {
{1, 2, 7},
{1, 3, 11},
{2, 5, 1},
{2, 4, 3},
{3, 4, 1},
{3, 6, 3},
{4, 5, 1},
{4, 7, 1},
{5, 7, 11},
{6, 7, 5}
};
for (auto& edge : input) {
int u = edge[0], v = edge[1], w = edge[2];
graph[u].push_back(make_pair(v, w));
graph[v].push_back(make_pair(u, w)); // Assuming undirected graph
}
int startVertex = 1;
vector<int> shortestDistances = dijkstra(graph, startVertex);
cout << "Shortest distances from vertex " << startVertex << ":\n";
for (int i = 1; i <= nodes; ++i) {
cout << "To " << i << " : ";
if (shortestDistances[i] == numeric_limits<int>::max()) {
cout << "unreachable";
} else {
cout << shortestDistances[i];
}
cout << "\n";
}
return 0;
}
Shortest distances from vertex 1:
To 1 : 0
To 2 : 7
To 3 : 10
To 4 : 9
To 5 : 8
To 6 : 13
To 7 : 10
¶Algorithm Explanation
Let’s see how Dijkstra’s Algorithm works stepbystep with the following graph.

Initialization:
Start Node: 1
Initial Distances: [infinity, 0, infinity, infinity, infinity, infinity, infinity, infinity] (with 1based indexing)
Active Vertices Set: {(0, 1)} (distance, node)

Iteration 1:
Current Node: 1
Active Vertices Set: {}
Update distances:
To 2 via 1: 0 + 7 = 7
To 3 via 1: 0 + 11 = 11
New Active Vertices Set: {(7, 2), (11, 3)}
Distances: [inf, 0, 7, 11, inf, inf, inf, inf]
 Iteration 2:
Current Node: 2
Active Vertices Set: {(11, 3)}
Update distances:
To 5 via 2: 7 + 1 = 8
To 4 via 2: 7 + 3 = 10
New Active Vertices Set: {(8, 5), (10, 4), (11, 3)}
Distances: [inf, 0, 7, 11, 10, 8, inf, inf]

Iteration 3:
Current Node: 5
Active Vertices Set: {(10, 4), (11, 3)}
Update distances:
To 7 via 5: 8 + 11 = 19 (not better than current infinity)
Distances: [inf, 0, 7, 11, 10, 8, inf, inf]

Iteration 4:
Current Node: 4
Active Vertices Set: {(11, 3)}
Update distances:
To 7 via 4: 10 + 1 = 11
To 3 via 4: 10 + 1 = 11 (not an improvement)
New Active Vertices Set: {(11, 3), (11, 7)}
Distances: [inf, 0, 7, 11, 10, 8, inf, 11]
 Iteration 5:
Current Node: 3
Active Vertices Set: {(11, 7)}
Update distances:
To 6 via 3: 11 + 3 = 14
New Active Vertices Set: {(11, 7), (14, 6)}
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]

Iteration 6:
Current Node: 7
Active Vertices Set: {(14, 6)}
No distance updates (already optimal).
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]

Iteration 7:
Current Node: 6
Active Vertices Set: {}
No distance updates (already optimal).
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]
This traces how the algorithm systematically explores the graph, continually updating the shortest paths from the start node to all other nodes based on the current known shortest paths. Each step ensures the algorithm only revisits a node if a shorter path to it is discovered, efficiently managing the active set for optimal updates.
¶Time Complexity of Dijkstra’s Algorithm
Dijkstra’s algorithm implemented with a set has a time complexity of O((V + E) log V)
, where V is the number of vertices and E is the number of edges. Using a priority queue, the time complexity remains the same. In both cases, each vertex is processed at most once, and the priority queue operations take logarithmic time. The choice between a set and a priority queue depends on the specific requirements of the application, with sets offering simplicity and priority queues potentially providing faster execution.
¶Space Complexity of Dijkstra’s Algorithm
The space complexity of Dijkstra’s algorithm is O(V)
, where V is the number of vertices in the graph. This space complexity arises from the need to store the distance array. Additionally, auxiliary data structures such as the priority queue or set used for managing vertices may also contribute to space usage, but they typically have a smaller impact compared to the distance array. Overall, the space complexity of Dijkstra’s algorithm is linear with respect to the number of vertices in the graph.
¶Applications of Dijkstra’s Algorithm

Navigation Systems: GPS devices and mapping applications like Google Maps use Dijkstra’s algorithm to find the shortest route between a starting point and a destination. This is essential for providing accurate and efficient navigation instructions to users.

Network Routing: Dijkstra’s algorithm is used in the routing protocols that govern the forwarding of IP packets across the Internet. For example, Interior Gateway Protocols (
IGPs
) likeOSPF
(Open Shortest Path First) andISIS
(Intermediate System to Intermediate System) use Dijkstra’s algorithm to calculate the shortest paths within an autonomous system (AS). 
**Flight Path Planning: **Airlines and air traffic controllers use Dijkstra’s algorithm to plan flight paths for aircraft, considering factors such as distance, air traffic, and weather conditions. This helps optimize flight routes, minimize fuel consumption, and ensure safety.

Robotics and Autonomous Vehicles: Dijkstra’s algorithm is employed in robotics and autonomous vehicle navigation systems to plan optimal paths for robots and vehicles to move from one location to another while avoiding obstacles and hazards.

Telecommunications: Telecommunication companies use Dijkstra’s algorithm to optimize the routing of data packets through communication networks, ensuring efficient transmission and minimizing latency.

Supply Chain Management: In logistics and supply chain management, Dijkstra’s algorithm is used to optimize transportation routes for goods and materials, minimizing costs and delivery times.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Depth First Search  DFS Algorithm with Practical Examples
Introduction to Tree Data Structure with Practical Examples
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

SEO  Search Engine Optimization
1

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 SEO
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development