Shortest Path algorithms
Do you use Google Maps? You may be wondering why I’m asking this, and you’d be right to think so. We make use of these technologies on a daily basis. Did you know that Google Maps effectively employs two Graph algorithms to determine the shortest path between Source and destination? These two algorithms are Dijkstra’s algorithm and the A* algorithm.
Additionally, there are some other algorithms that are used for finding the shortest path. And we’ll talk about this algorithm in this blog.
So what is the shortest path algorithm?? As you read earlier about the Google Maps example you will surely get an idea about the problem. So The shortest path problem is about finding a path between vertices in a graph such that the total sum of the weights of the edges is minimum.
A number of researchers contributed their expertise to this topic and developed specific algorithms. Bellman-Ford and Dijkstra, among other scientists, proposed a method for this issue. Each has certain advantages over the others as well as some drawbacks. We will thus talk about their strategy for resolving this issue in this blog.
First, we will discuss Dijkstra’s Algorithm.
Dijkstra’s Algorithm
I hope that you have prior knowledge about the basic graph structure. If not then read this article and after that continue with this topic.
- Dijkstra’s Algorithm is a Greedy algorithm that basically starts at the node that you choose (the source node) and it analyzes the graph to find the shortest path between that node and all the other nodes in the graph.
- The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
- Once the algorithm has found the shortest path between the source node and another node, that node is marked as “visited” and added to the path.
- The process continues until all the nodes in the graph have been added to the path. This way, we have a path that connects the source node to all other nodes following the shortest path possible to reach each node.
While trying to comprehend these theoretical principles, it appears that you are becoming bored and uncomfortable😁. No worries, we’ll understand this concept with a practical example to help you comprehend this method.
Consider the above situation where a person wants to reach their destination. The edges indicate the distance between the two cities. There are many paths from which he/she can reach the destination. But in order to save money and time that person will choose the shortest path.
So Solution for this problem can be given by Dijkstra’s algorithm greedy strategy.
We must keep a graph structure in order to address this issue. The solution to this problem will include creating a tree structure for that graph structure. The following are the steps to produce this solution:
- Beginning with the starting point
- Choose one vertex at a time that is the closest to the starting point in terms of edge weight.
- If the connecting edge does not form a cycle, add the chosen vertex to the tree structure.
- Up to the destination, keep adding nearby fringe vertices to the tree.
The picture provided below demonstrates how pathways will be chosen to go to the destination city. The red path indicates the shortest path taken by the person to reach the destination.
The Time Complexity of Dijkstra’s Algorithm is O(V²) but with a min-priority queue it drops down to O(O+E logV).
Bellman–Ford Algorithm
Bellman Ford’s algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph. It depends on the following concept: Shortest path contains at most n-1 edges because the shortest path couldn’t have a cycle.
So why shortest path shouldn’t have a cycle? There is no need to pass a vertex again because the shortest path to all other vertices could be found without the need for a second visit for any vertices
This algorithm aims to eliminate a significant flaw in Dijkstra’s algorithm. Negative weights prevented Dijkstra’s algorithm from operating properly. as it has a variety of uses. As a result, the Bellman-Ford method is compatible with both positive and negative network weights.
How does It work?
- The algorithm determines the shortest pathways from the bottom up, just as other Dynamic Programming Problems. The shortest paths with a maximum of one edge are initially determined.
- It then determines the shortest pathways with a maximum of two edges, and so on. The shortest pathways with at most i edges are determined following the i-th iteration of the outer loop
- Any simple path may have a maximum of |V| — 1 edge, therefore the outer loop runs |v| — 1 time.
- According to the theory, if we have computed the shortest pathways with at most i edge, and there isn’t a negative weight cycle, then iterating over all edges will result in the shortest path with at most (i+1) edges.
The above algorithm’s example is explained below……
Step 1: Let the given source vertex be 0. Initialize all distances as infinite, except the distance to the source itself. The total number of vertices in the graph is 5, so all edges must be processed 4 times.
Step 2: Let all edges be processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). We get the following distances when all edges are processed the first time. The first row shows the initial distances. The second row shows distances when edges (B, E), (D, B), (B, D) and (A, B) are processed. The third row shows distances when (A, C) is processed. The fourth row shows when (D, C), (B, C) and (E, D) are processed.
Step 3: The first iteration guarantees to give all shortest paths which are at most 1 edge long. We get the following distances when all edges are processed a second time (The last row shows the final values).
Step 4: The second iteration guarantees to give all shortest paths which are at most 2 edges long. The algorithm processes all edges 2 more times. The distances are minimized after the second iteration, so the third and fourth iterations don’t update the distances.
A very important application of Bellman-Ford is to check if there is a negative cycle in the graph, Time Complexity of the Bellman-Ford algorithm is relatively high, it is O( V.E ) where E=V² so the ultimate time complexity will be O(V³).
I hope this blog is helpful for you guys. See you in the next blog🤩.
Written By —
Aryan Mamidwar
Atharva Mugalikar
Vivek Ghuge
Divija Godse
