Dijkstra’s algorithm is a fundamental and effective method for determining the shortest route in a graph with non-negative weighted edges. It is the most commonly utilized method for discovering the optimal answer for shortest pathfinding dilemmas in graph theory. Whether you are designing GPS navigation tools or developing AI pathfinding solutions, Dijkstra’s algorithm can be employed for both efficiency and swift execution. In this article, we will explore what Dijkstra’s algorithm comprises, how it operates, its pseudocode, a practical example, and its implementation across various programming languages. Additionally, we will address the benefits, drawbacks, applications, and a comparison with the Bellman-Ford algorithm.
Dijkstra’s Algorithm is a search method for graphs utilized to locate the shortest path from a starting node to all other nodes in a weighted graph, where all edge weights are non-negative. It was developed by the Dutch computer scientist Edsger W. Dijkstra. Generally, it functions by gradually exploring the nearest unvisited node and refreshing the shortest path to each adjacent node. Once the shortest path to a node is identified, it is marked as visited. Subsequently, the algorithm proceeds to determine the shortest path to a specific target by visiting all other nodes that haven’t been explored yet. Dijkstra’s algorithm exemplifies a greedy algorithm and is applicable only to weighted graphs with positive edge weights.
How Dijkstra’s Algorithm Operates
Dijkstra’s Algorithm requires a graph and an initial vertex to commence the search for the shortest path. This algorithm adheres to a greedy methodology, meaning it opts for the optimal selection at each juncture and chooses the node with the least distance.
Below is a detailed explanation of how Dijkstra’s algorithm functions.
Step 1: Initialization
Initially, select a starting node known as the source node.
Then, assign a distance of 0 to the source and represent the distance to all other nodes as infinity.
Next, label all nodes as unvisited.
Generate a priority queue or a min-heap to monitor all nodes with the shortest distances.
Step 2: Visit the Current Node
Start with the source node in the beginning.
For each of its unvisited neighboring nodes, compute the distance from the source node.
If the new distance is smaller than the previously calculated one, update it accordingly.
Step 3: Mark as Visited
Once all neighboring nodes have been examined, mark the current node as visited.
The nodes that have been visited will not undergo re-examination since their shortest distances are already established.
Step 4: Repeat
Select the next unvisited node that has the smallest distance.
Repeat steps 2 and 3 until all nodes are marked as visited or until you reach the target node.
Step 5: Final Output
The algorithm concludes once all possible shortest paths from the source node are identified.
You will then possess the shortest distance to each node and, if previous nodes were tracked, you can also reconstruct the shortest paths.
Next, let’s delve into the concept of a min-heap, which we referenced above in Dijkstra’s algorithm:
Min-Heap
A min heap is a complete binary tree wherein the value of each parent node is less than or equal to the values of its child nodes. This ensures that the smallest element resides at the root of the heap. Min heaps are often implemented through arrays for effective storage and indexing. Insertion and deletion operations uphold the heap property via “heapify” processes. They are frequently utilized in algorithms such as Dijkstra’s and in priority queues. The time complexity for both insertion and deletion in a min-heap is O(log n), while retrieving the minimum takes O(1).
Dijkstra’s Algorithm – Pseudocode
function Dijkstra(Graph, source):
create distance map: set all distances to infinity set distance[source] = 0
create a priority queue and add source with distance 0
while the priority queue is not empty: current_node = node with smallest distance in queue mark current_node as visited
for each unvisited neighbor of current_node: tentative_distance = distance[current_node] + weight(current_node, neighbor)
if tentative_distance < distance[neighbor]: distance[neighbor] = tentative_distance add neighbor to the queue with updated distance
return distance
Become a Python Certified Professional!
Enroll now to master Python with expert-led live sessions.
In this illustration, we will determine the shortest distance from City A to every other city.
Here is the map depicting the cities along with the distances between them.
Cities (Nodes): A, B, C, D, E, F Edges and Weights (Distances):
From
To
Distance
A
B
4
A
C
2
A
D
1
B
E
5
C
F
3
D
F
8
D
E
5
E
F
2
Next, here is a detailed procedure to address the challenge of finding the shortest route.
Step 1: Initialization
Begin at node A, establishing its distance to 0 since it is the source node.
Set the distances of all remaining nodes to infinity to indicate that they are not accessible from the starting node initially.
Utilize the min-heap data structure to identify the city with the currently shortest distance.
City
Distance from A
Visited
Path
A
0
No
A
B
infinity
No
–
C
infinity
No
–
D
infinity
No
–
E
infinity
No
–
F
infinity
No
–
The current Min Heap now is [(0, A)].
Step 2: Explore Nodes or Cities, and Refresh the Path
Now, examine each city sequentially while continuously updating the shortest distance.
1. Explore City A
Initially, City A is visited as it holds the smallest value of 0 post-initialization. Thus, we will insert node A into the min-heap.
Node A is the sole entry in the min heap.
Now, we will probe all the neighbors of city A.
A -> B: dist[B] = min(0 + 4) = 4
A -> C: dist[C] = min(0 + 2) = 2
A -> D: dist[D] = min(0 + 1) = 1
Thus, refresh the distance:
B’s distance is now 4
C’s distance is now 2
D’s distance is now 1
These updated nodes (B: 4, C: 2, D: 1) will subsequently be inserted into the min heap to be processed based on their current shortest distances.
City
Distance
Visited
Path
A
0
Yes
A
B
4
No
A → B
C
2
No
A → C
D
1
No
A → D
E
infinity
No
–
F
infinity
No
–
Thus, Min Heap: [(1, D), (2, C), (4, B)]
2. Explore City D
In Dijkstra’s algorithm, we consistently select the node with the least current distance from the min heap. Consequently, after inserting cities B (4), C (2), and D (1) into the min heap, D has the smallest distance (1) making it the next node to be removed (visited).
Now, extract (1, D) from the heap as D currently has the minimum distance.
Subsequently, analyze all neighbors of D.
D -> E: dist[E] = min(1 + 5) = 6
D -> F: dist[F] = min(1 + 8) = 9
Thus, refresh the distances:
E’s distance is set to 6.
F’s distance is updated to 9.
These new distances (E: 6, F: 9) will be added to the heap for subsequent processing.
City
Distance
Visited
Path
A
0
Yes
A
B
4
No
A → B
C
2
No
A → C
D
1
Yes
A → D
E
6
No
A → D → E
“““html
F
9
No
A → D → F
Current Min Heap: [(2, C), (4, B), (6, E), (9, F)]
3. Access Node C
After handling D (with distance 1), the heap updates to: (4, B), (2, C), (6, E), (9, F). Consequently, remove (2, C) from the heap since C now has the least distance.
Next, investigate all nearby locations of C.
C -> F: dist[F] = min(2 + 3) = 5
Hence, modify the distance:
F’s distance to 5.
Consequently, (5, F) is pushed into the heap to reflect the shorter route via C.
City
Distance
Visited
Path
A
0
Yes
A
B
4
No
A → B
C
2
Yes
A → C
D
1
Yes
A → D
E
6
No
A → D → E
F
5
No
A → C → F
Min Heap: [(4, B), (6, E), (9, F), (5, F)]
4. Access Node B
Following the earlier steps, the min heap now contains: (5, F), (6, E), (4, B). Thus, remove (4, B) from the heap as B now has the minimum distance.
Next, explore all neighbouring nodes of B.
B -> E: dist[E] = min(4 + 5) = 9
However, E already has a superior and lesser path of 6, so there’s no need to change E.
City
Distance
Visited
Path
A
0
Yes
A
B
4
Yes
A → B
C
2
Yes
A → C
D
1
Yes
A → D
E
6
No
A → D → E
F
5
No
A → C → F
Min Heap: [(5, F), (6, E)]
5. Access Node F
At this point, remove (5, F) from the heap, as F now has the minimal distance.
After that, all surrounding nodes of F have already been processed.
City
Distance
Visited
Path
A
0
Yes
A
B
4
Yes
A → B
C
2
Yes
A → C
D
1
Yes
A → D
E
6
No
A → D → E
F
5
Yes
A → C → F
Min Heap: [(6, E)]
6. Access Node E
Now, remove (6, E) from the heap because E has the least distance at present.
Then, all the adjacent nodes of E have been visited and possess a shorter path, so there won’t be any modifications.
City
Distance
Visited
Path
A
0
Yes
A
B
4
Yes
A → B
C
2
Yes
A → C
D
1
Yes
A → D
E
6
Yes
A → D → E
F
5
Yes
A → C → F
Currently, the Min Heap is devoid of any elements, signifying the end of the algorithm.
Step 3: Final Shortest Routes from City A to All Other Locations
City
Distance
Visited
Path
A
0
Yes
A
B
4
Yes
A → B
C
2
Yes
A → C
D
1
Yes
A → D
E
6
“““html
Affirmative
A → D → E
F
5
Affirmative
A → C → F
Therefore, the table presented above is the conclusive update for the shortest routes originating from City A.
Time and Space Complexity of Dijkstra’s Algorithm
This section provides a concise overview of the time and space complexity associated with Dijkstra’s Algorithm.
Time Complexity of Dijkstra’s Algorithm
The time complexity of Dijkstra’s Algorithm relies on two main components:
The data structure utilized for the priority queue (min-heap).
The graph representation via a matrix or an adjacency list.
Now, let’s denote
V = number of vertices (nodes)
E = number of edges
1. Utilizing a min-heap (priority queue) + adjacency list
The overall time complexity when employing a min-heap (priority queue) alongside an adjacency list is O((V + E) * log V). Each vertex can be added to the heap at most once, contributing O(V log V) to the complexity, while each edge can trigger an insertion in the heap, which results in O(E log V). Additionally, the complexity for heap operations (insert, pop) is O(log V).
This variant represents the most efficient and frequently used form of Dijkstra’s algorithm.
2. Utilizing an adjacency matrix + no heap (basic array for minimum search)
The total time complexity when using an adjacency matrix without a heap is O(V^2), since discovering the minimal distance between each node takes O(V) time, repeated for every vertex, leading to O(V*V) total time.
This approach is slower and less efficient compared to the previous one.
Space Complexity of Dijkstra’s Algorithm
Space complexity also varies based on the specific version of Dijkstra’s Algorithm applied:
1. Utilizing a min-heap (priority queue) + adjacency list
The space complexity of Dijkstra’s Algorithm is O(V+E), as the min-heap consumes O(V) space while the adjacency list uses O(E) for storing the graph.
2. Utilizing an adjacency matrix + no heap (basic array for minimum search)
The space complexity of Dijkstra’s Algorithm is O(V^2), due to the array that occupies O(V) space and is repeated for each vertex.
The following table illustrates the precise understanding of time and space complexity for Dijkstra’s Algorithm.
Data Structure Utilized
Time Complexity
Space Complexity
Min Heap + Adjacency List
O((V + E) log V)
O(V + E)
Basic Array + Matrix
O(V²)
O(V²)
Implementation of Dijkstra’s Algorithm
1. Implementation of Dijkstra’s Algorithm in C++
Cpp
Code Copied!
var isMobile = window.innerWidth “);
editor70741.setValue(decodedContent); // Set the default text
editor70741.clearSelection();
editor70741.setOptions({
maxLines: Infinity
});
function decodeHTML70741(input) {
var doc = new DOMParser().parseFromString(input, “text/html”);
return doc.documentElement.textContent;
}
// Function to copy code to clipboard
function copyCodeToClipboard70741() {
const code = editor70741.getValue(); // Get code from the editor
navigator.clipboard.writeText(code).then(() => {
jQuery(“.maineditor70741 .copymessage”).show();
setTimeout(function() {
jQuery(“.maineditor70741 .copymessage”).hide();
}, 2000);
}).catch(err => {
console.error(“Error copying code: “, err);
});
}
function runCode70741() {
var code = editor70741.getSession().getValue();
function closeoutput70741() {
var code = editor70741.getSession().getValue();
jQuery(".maineditor70741 .code-editor-output").hide();
}
// Add event listeners to the buttons
document.getElementById("copyBtn70741").addEventListener("click", copyCodeToClipboard70741);
document.getElementById("runBtn70741").addEventListener("click", runCode70741);
document.getElementById("closeoutputBtn70741").addEventListener("click", closeoutput70741);
Result:
Clarification:
The preceding C++ application demonstrates how Dijkstra’s Algorithm can be utilized in C++ programming to ascertain the shortest routes from a source node to all other nodes in a weighted graph utilizing a min-heap.
An adjacency list (vector<pair<int, int>> adj[]) is employed in the program to depict the graph, where each pair signifies a neighbor and the edge weight.
The dijkstra() function is responsible for managing a distance array and modifying it by probing the nearest distance node from the priority queue first.
Ultimately, subsequent to examining all nodes, the main function outputs the shortest paths from the source 0 to every other node.
2. Application of Dijkstra’s Algorithm in JAVA
Java
Code Copied!
var isMobile = window.innerWidth “);
editor62971.setValue(decodedContent); // Set the default text
editor62971.clearSelection();
editor62971.setOptions({
maxLines: Infinity
});
function decodeHTML62971(input) {
var doc = new DOMParser().parseFromString(input, “text/html”);
return doc.documentElement.textContent;
}
// Function to copy code to clipboard
function copyCodeToClipboard62971() {
const code = editor62971.getValue(); // Retrieve code from the editor
navigator.clipboard.writeText(code).then(() => {
// alert(“Code copied to clipboard!”);
function closeoutput62971() {
var code = editor62971.getSession().getValue();
jQuery(".maineditor62971 .code-editor-output").hide();
}
// Attach event listeners to the buttons
document.getElementById("copyBtn62971").addEventListener("click", copyCodeToClipboard62971);
document.getElementById("runBtn62971").addEventListener("click", runCode62971);
document.getElementById("closeoutputBtn62971").addEventListener("click", closeoutput62971);
``````html
runCode62971);
document.getElementById("closeoutputBtn62971").addEventListener("click", closeoutput62971);
Outcome:
Clarification:
The provided JAVA code illustrates how Dijkstra&rsquo;s Algorithm is applied in JAVA coding to discover the shortest routes from a source node to every other node in a weighted graph utilizing a min-heap.
An adjacency list (List<List<int[]>>) is employed to illustrate the graph, where each int[] keeps a neighbor along with the corresponding weight.
Moreover, a tailored Pair class is utilized to hold the (distance, node) pairs and facilitate sorting based on distance using compareTo.
Lastly, the main function outputs the shortest paths from the source node to each individual node.
3. Implementation of Dijkstra&rsquo;s Algorithm in Python
Python
Code Copied!
var isMobile = window.innerWidth “);
editor57084.setValue(decodedContent); // Set the default text
editor57084.clearSelection();
editor57084.setOptions({
maxLines: Infinity
});
function decodeHTML57084(input) {
var doc = new DOMParser().parseFromString(input, “text/html”);
return doc.documentElement.textContent;
}
// Function to copy code to clipboard
function copyCodeToClipboard57084() {
const code = editor57084.getValue(); // Get code from the editor
navigator.clipboard.writeText(code).then(() => {
jQuery(“.maineditor57084 .copymessage”).show();
setTimeout(function() {
jQuery(“.maineditor57084 .copymessage”).hide();
}, 2000);
}).catch(err => {
console.error(“Error copying code: “, err);
});
}
function runCode57084() {
var code = editor57084.getSession().getValue();
function closeoutput57084() {
var code = editor57084.getSession().getValue();
jQuery(".maineditor57084 .code-editor-output").hide();
}
// Attach event listeners to the buttons
document.getElementById("copyBtn57084").addEventListener("click", copyCodeToClipboard57084);
document.getElementById("runBtn57084").addEventListener("click", runCode57084);
document.getElementById("closeoutputBtn57084").addEventListener("click", closeoutput57084);
Outcome:
Clarification:
The above Python code demonstrates how Dijkstra&rsquo;s Algorithm is implemented in Python programming for determining the shortest paths from a source node to every other node in a weighted graph using a min-heap (heapq).
An adjacency list (adj) is employed to represent the graph, where each node has a collection of tuples (neighbor, weight).
The algorithm revises the shortest path (dist[]) by exploring all nearest unvisited nodes from the heap.
Ultimately, the function displays the shortest paths from the source to each node.
Benefits of Dijkstra&rsquo;s Algorithm
Provides Optimal Solution: Dijkstra&rsquo;s algorithm consistently generates the least-cost or shortest route from a source node to all other nodes within a graph, provided that the edge weights are nonnegative.
Efficient: Utilizing a min-heap (i.e., priority queue), Dijkstra&rsquo;s algorithm is effective and maintains a favorable time complexity.
Widely Utilized Algorithm: Dijkstra&rsquo;s algorithm is frequently implemented in routing protocols and GPS systems, as it yields a path with minimal cost and time.
“““html Can be utilized with Directed and Undirected Graphs: Dijkstra’s algorithm is applicable to directed and undirected graphs (must possess positive edge weights).
Drawbacks of Dijkstra’s Algorithm
Does not support Negative Weights: Dijkstra’s algorithm is ineffective with graphs that include negative edge weights; it either fails or produces erroneous outputs.
Not Efficient for Large Dense Graphs: It exhibits poor performance when used on dense graphs characterized by numerous edges and nodes, even with a min-heap implementation.
Single Source Node Limitation: Dijkstra’s algorithm calculates the shortest path solely from one source node at any given time. It isn’t suitable for scenarios requiring all-pairs shortest paths.
Lacks Actual Path Tracking: The standard implementation of this algorithm does not keep the actual path; it merely retains the distances between nodes. Additional logic is necessary to track the actual path route.
Uses of Dijkstra’s Algorithm
Dijkstra’s algorithm is employed by GPS-based navigation systems, such as Google Maps, Waze, and various GPS devices to identify and calculate the shortest route from the start point to the destination. In these systems, travel time or road distance serves as edge weights.
The algorithm is also utilized for network routing in routing frameworks like OSPF (Open Shortest Path First) to identify the most efficient and shortest pathway for transmitting data packets. This significantly aids in minimizing congestion across routers.
Urban planners apply Dijkstra’s algorithm to strategize traffic flow, determine signal timing, or plan road construction aimed at alleviating congestion and reducing travel duration.
Dijkstra’s algorithm is also employed by AI pathfinding systems, primarily in video games and simulations, to strategically and effectively navigate through mapped spaces.
Companies such as FedEx, Amazon, etc., implement Dijkstra’s algorithm to identify the shortest routes, optimizing costs related to time and fuel. They also use it for planning routes within warehouses.
Boost Your Tech Career with Free Python Certification!
Sign Up Now! Learn Python Online – Anytime, Anywhere, for Free!
The following table compares Dijkstra’s and Bellman-Ford algorithms across various parameters, including suitability for different graph types, edge weights, time complexities, space requirements, and specific applications. This comparison helps clarify when and why to prefer a particular algorithm based on graph characteristics and the problem at hand.
Feature
Dijkstra’s Algorithm
Bellman-Ford Algorithm
Graph Type
Weighted, both directed and undirected
Weighted, directed
Edge Weights
Only non-negative
Accommodates negative weights
Negative Cycle Detection
Not applicable
Applicable
Time Complexity
O((V+E)*log V) with min-heap
O(V* E)
Space Complexity
O(V^2)
O(V^2)
Algorithm Type
Greedy
Dynamic Programming
Shortest Path Assurance
Yes (only for non-negative weights)
Yes (even with negative weights)
Path Reconstruction Assistance
Requires predecessor tracking
Requires predecessor tracking
Use Case
Rapid routing in non-negative graphs
Generic graphs possibly involving negatives
Summary
Dijkstra’s algorithm is the most prevalent pathfinding technique employing a graph data structure. It is extensively utilized in various real-world applications to identify the shortest paths, thereby conserving time and resources, as well as addressing challenges like efficient path planning, navigation, and routing. This algorithm performs efficiently with a min-heap; however, it has certain limitations, such as its inability to handle negative weights and the requirement for additional logic to record actual route paths. By mastering Dijkstra’s algorithm along with its operations, pseudocode, implementations, merits, demerits, and applications, you can efficiently apply this technique to any problem associated with shortest-path computation in programming.
Dijkstra’s Algorithm – FAQs
Q1. Can Dijkstra’s Algorithm handle negative edge weights?
No, Dijkstra’s Algorithm is unable to manage negative weights, as it will lead to incorrect outcomes when such edge weights are utilized.
Q2. What data structure is employed in Dijkstra’s Algorithm?
A priority queue is utilized in Dijkstra’s algorithm to effectively choose the next node with the minimal tentative distance.
Q3. Does Dijkstra’s Algorithm determine the shortest path from one source to all nodes?
Yes. It computes the shortest distance from a single source to all other nodes within the graph.
Q4. Is Dijkstra’s Algorithm quicker than Bellman-Ford?
Yes, for graphs devoid of negative weights, Dijkstra’s Algorithm outperforms Bellman-Ford, particularly when implemented with a min-heap.
Q5. Can Dijkstra’s Algorithm be implemented in undirected graphs?
Yes. It is applicable to both directed and undirected graphs, provided that the weights are non-negative.
To provide the best experiences, we use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us to process data such as browsing behavior or unique IDs on this site. Not consenting or withdrawing consent, may adversely affect certain features and functions.
Functional
Always active
The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.
Preferences
The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.
Statistics
The technical storage or access that is used exclusively for statistical purposes.The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.
Marketing
The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.
