Here “Cost” means the number of nodes in the route or the summation of costs on each path. A path can have one or multiple edges. The connection between two vertices is called “edge”. There are various types of shortest path algorithms, like Dijkstra’s Algorithm, Bellman-Ford algorithm, etc. Here, we discuss about Dijkstra’s Algorithm Let’s look at the following weighted Graph:
The term “Weighted” means moving costs from one node to another. For example, moving from node 1 to node 2, the cost or weight is 1. The path between node 1 to node 2 is called the edge. “Undirected” means you can move one node to another and back to the previous node. So, if we try to find all the routes from node 1 to node 7, then it will be:
Among these four routes, we can see that the first route will cost us 7. So, it is the shortest path in terms of cost.
How Dijkstra’s Algorithm Works
Dijkstra algorithm can find the shortest distance in both directed and undirected weighted graphs. This Algorithm is greedy because it always chooses the shortest or closest node from the origin. The term “greedy” means that among a set of outcomes or results, the Algorithm will choose the best of them. Here, we are trying to find the shortest paths among all other routes. So, Dijkstra’s Algorithm finds all the shortest paths from a single destination node. As a result, it behaves like a greedy algorithm. In the “example” section below, you’ll see the step-by-step approach. It works as follows: Step 1) Initialize the starting node with 0 costs and the rest of the node as Infinity Cost. Step 2) Maintain an array or list to keep track of the visited nodes Step 3) Update the node cost with the minimum cost. It can be done by comparing the current cost with the path cost. (Demonstration is shown in the example section) Step 4) Continue step 3 until all the node is visited. After completing all these steps, we will find the path that costs a minimum from source to destination.
Difference Between Dijkstra and BFS, DFS
The main difference between Dijkstra and BFS-DFS is that Dijkstra is the shortest pathfinding algorithm, and BFS, DFS is the pathfinding algorithm. In general cases, BFS and DFS don’t consider the cost while finding the path. So, these algorithms can’t guarantee the shortest path.
2D grid demonstration of how BFS works
This demonstration indicates that BFS only finds the path. However, it does not care about the path’s weight. BFS (Breadth-First Search) assumes that traveling from one node to another node will cost only 1. But let us see an example graph:
Here, it finds a path in level 2. BFS traverses the Graph in level order. So, it travels like: Step 1) Start from node “1” and visit all the adjacent nodes 2,3,4 Step 2) Mark node 2,3,4 as level 1 and visit their adjacent nodes. It will continue exploring all the adjacent nodes until it reaches the destination node. In terms of DFS, it will traverse the path from 1 to 7 like the following:
1→2→3→7 (Original Cost 10, DFS cost 3) 1→2→6→7 (Original Cost 7, DFS cost 3) 1→3→7 (Original Cost 8, DFS cost 2) 1→4→5→7 (Original Cost 13, DFS cost 3)
As we see, DFS calculates its path cost with the number of depth or number of edges. DFS does the following:
DFS can find a path from source (starting vertex) to destination. It cannot guarantee whether the path discovered from source node to destination is the shortest path or not.
However, in terms of the Dijkstra Algorithm, it will choose edges based on their cost. As a greedy algorithm, it will pick the best or minimum cost paths.
Example of Dijkstra’s Algorithm
Dijkstra’s Algorithm uses the cost or weight to calculate the total cost of the path.
The target of Dijkstra’s Algorithm is to minimize this total cost or weight. In the example shown above, we find the best paths from node 1 to node 7, then calculate all the costs. In Dijkstra’s Algorithm, it will find the shortest paths by calculating weights. It will not search for all possible paths. Let us demonstrate Dijkstra’s Algorithm with an example. For example, you’ve been asked to find the shortest path from node 1 to 7. For this process, steps are given below: Step 1) Initialize the starting node cost to 0. Rest of the node, assign “Inf”. It means no path exists between the starting vertex (the source) and the node, or the path is not visited yet.
Step 2) When you select node 1, it will be marked as visited. Then update all the adjacent neighbors of node 1. 2,3,4 are the neighboring nodes of node 1. While updating a cost, we need to follow the procedure below:
We can update each node’s cost using the above formula. For example, we were at node 1, and we needed to update the cost of its adjacent node 2,3,4. After updating, the cost or weight will look like this:
Step 3) For node “2”, neighbors are 6 and 3. We are updating the cost at “6” by comparing infinity (current value). The cost of node 2 + path cost from 2 to 6. Simply saying, node “6” will have the cost of 1+3 or 4.
Node 3 is a neighbor of node 2. However, we calculated its cost in the previous step, which was 7. Now, if our path is 1-2-3, node 3 will have a cost of 10. Path 1-2-3 will cost 10, while 1 to 3 will cost 7. Step 4) For node 3, the neighboring node is 7. So, comparing the current value of node 7 with the path cost (7+1) or 8, we will update the cost of node 7. That is 8. So, we find a path from node 1 to node 7, and it is 1→ 3→ 7. The cost is 8. Step 5) For node 4, we will update its adjacent node cost accordingly. So, node “5” will have an updated cost of 8. After step 4,5, it will look like this:
Now, the path 1-3-7 has the cost of 8 (previously). Node “7” wasn’t marked visited because we can reach node “7” from node “6”. The path “1-2-6” had a cost of 4. So the path 1-2-6-7 will have the cost of 7. As 7 < 8, that’s why the shortest path from source vertex “1” to destination vertex “7” will be 1-2-6-7, and the cost is 7. Previously it was 1-3-7, and the cost was 8. So, the final Graph will look like this:
The edge marked with a black line is our shortest path from 1 to 7, and it will cost us 7.
Pseudo Code Dijkstra’s Algorithm
Here’s the pseudo-code for Dijkstra’s Algorithm
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ implementation Dijkstra’s Algorithm
To implement Dijkstra’s algorithm using C++, here’s the code:
#include <bits/stdc++.h> using namespace std; #define size 7 int minimumDistance(int distance[], bool visited[]) { int min = INT_MAX; int min_index = INT_MAX; for (int i = 0; i < size; i++) { if (!visited[i] & amp; & distance[i] <= min) { min = distance[i]; min_index = i; } } return min_index; } void printParentPath(int parent[], int i) { if (parent[i] == -1) { return; } printParentPath(parent, parent[i]); cout « i + 1 « " “; } void dijkstra(int graph[size][size], int source) { int distance[size]; bool visited[size]; int parent[size]; for (int i = 0; i < size; i++) { parent[0] = -1; distance[i] = INT_MAX; visited[i] = false; } distance[source] = 0; for (int i = 0; i < size - 1; i++) { int U = minimumDistance(distance, visited); visited[U] = true; for (int j = 0; j < size; j++) { int curr_distance = distance[U] + graph[U][j]; if (!visited[j] & amp; & graph[U][j] & amp; & curr_distance < distance[j]) { parent[j] = U; distance[j] = curr_distance; } } } cout « “Vertex\t\tDistance\tPath” « endl; for (int i = 1; i < size; i++) { cout « source + 1 « “->” « i + 1 « “\t\t” « distance[i] « “\t\t” « source + 1 « " “; printParentPath(parent, i); cout « endl; } } int main() { int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0}, {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0}, {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3}, {0, 0, 0, 0, 5, 3, 0}}; dijkstra(graph, 0); }
Output:
Vertex Distance Path
1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python implementation Dijkstra’s Algorithm
To implement Dijkstra’s algorithm using python, here’s the code:
num_of_vertex = 7 def minimumDistance(distance, visited): _min = 1e11 min_index = 1e11 for i in range(num_of_vertex): if not visited[i] and distance[i] & lt; = _min: _min = distance[i] min_index = i return min_index def printParentNode(parent, i): if parent[i] == -1: return printParentNode(parent, parent[i]) print(”{} “.format(i + 1), end = “”) def dijkstra(graph, src): distance = list() visited = list() parent = list() for i in range(num_of_vertex): parent.append(-1) distance.append(1e11) visited.append(False) distance[src] = 0 for i in range(num_of_vertex - 1): U = minimumDistance(distance, visited) visited[U] = True for j in range(num_of_vertex): curr_distance = distance[U] + graph[U][j] if not visited[j] and graph[U][j] and curr_distance & lt; distance[j]: parent[j] = U distance[j] = curr_distance print(“Vertex\t\tDistance\tPath”) for i in range(num_of_vertex): print(”{}->{}\t\t{}\t\t{} “.format(src + 1, i + 1, distance[i], src + 1), end = “”) printParentNode(parent, i) print(””) graph = [ [0, 1, 7, 6, 0, 0, 0], [1, 0, 9, 0, 0, 3, 0], [7, 9, 0, 0, 0, 0, 1], [6, 0, 0, 0, 2, 0, 0], [0, 0, 0, 2, 0, 0, 0], [0, 3, 0, 0, 0, 0, 3], [0, 0, 0, 0, 5, 3, 0] ] dijkstra(graph, 0)
Output:
Vertex Distance Path
1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
We can see that the Algorithm calculates the shortest distance from the source node.
Application of Dijkstra Algorithm
The Dijkstra Algo has a large set of usages. Among those, it is widely used, in the field of networking. Here’s some of the real-life usage of Dijkstra’s Algorithm: Dijkstra in Google map: Basically, this Algorithm is the backbone for finding the shortest paths. As we can see from the above code snippet output.
Google doesn’t use the simple Dijkstra algorithm. Instead, it uses a modified version. When you select a destination, it shows you multiple paths in the Google Map. Among these paths, some paths are sorted out for the user. These paths selected are based on the “time”. So, “time” is an edge cost for the shortest path. Dijkstra in IP routing: IP routing is a networking terminology. It means how your data packet is being sent to the receiver via different paths. These paths consist of routers, servers, etc. In IP routing, there are different types of protocols. These protocols help the router find the shortest paths to send the data. One of the protocol names is “OSPF (Open Shortest Path First)”. OSPF uses dijkstra algorithm. The router maintains a table of routes. Each router shares its table with neighbor routers. After receiving the updated table, they must calculate all the paths again. At that time, the router uses the Dijkstra Algorithm.
Limitation of Dijkstra’s Algorithm
Dijkstra algorithm cannot guarantee the shortest path in the negative edge graph. Dijkstra algorithm follows these methodologies:
One shortest path will be taken from one node to another. Once the shortest path between two nodes is selected, it will not be calculated again.
Here, notice two examples with negative edges.
In the left Graph, there are three vertices. Dijkstra will run on the Graph like the following: Step 1) Starting vertex “1” will be initialized to zero. The other nodes will have infinity.
Step 2) Mark Node “1” as visited and include it in the shortest path. Step 3) The distance of the source node 1 to nodes “2” and “3” is set to infinity, as the shortest path is yet to be calculated. So, any path that will cost less than infinity will be added to the shortest path (greedy approach). Step 4) Updating the distance from source vertex or source node “1” to “2”. The Current weight will be 5 (5<infinity). Similarly, update the distance from node “1” to “3” with the weight of 3.
Step 5) Now if we check the shortest distances from node “1,” we find that 5 is the shortest distance for edge 1–> 2. So, node “2” will be marked as visited. Similarly, node “3” will also be marked as visited as the shortest distance is 3. However, If we observe, there’s a path 1-3-2 that will cost only 2. But the Dijkstra shows that from node “1” to node “2,” the shortest distance is 5. So, Dijkstra failed to calculate the shortest distance correctly. The reason it happened is that, Dijkstra is a greedy algorithm. So, once a node is marked visited, it will not be reconsidered, although there might be a shorter path available. This issue only occurs when the edges have negative costs or negative weight edges Dijkstra fails to calculate the shortest path between two nodes in this scenario. As a result, this Algorithm has some drawbacks. To solve this negative edge problem, another algorithm called “Bellman-Ford Algorithm” is used. That Algorithm can work with negative edges.
Dijkstra’s Algorithm Complexity
The implementation above used two “for” loops. These loops run for the number of vertices. So, the time complexity is O(V2). Here, the term “0” means a notation that gives an assumption for the Dijkstra algorithm. We can store the Graph using the “Priority Queue”. A priority queue is a binary heap data structure. It will be more efficient than a 2D matrix. An edge that will have a minimum cost will have a high priority. Then the time complexity will be O(E log(V)). Here, E is the number of edges, and V is the number of vertices. The space complexity is O(V2), as we are using an adjacency matrix (2D array). Space complexity can be optimized using an adjacency list or queue data structure.
