Shortest Paths
Hi, I am back after a very long time, actually was thinking about what’s to write next, and I have found something, reading and learning about algorithms for the past few days, I was thinking that why we care about the ‘Shortest Path’ so much in the field of algorithms and here are the few reasons,
The ‘Shortest Path’ as the name says, is an algorithm for finding the shortest distance between any two vertices, or points, it's an old human urge to minimize its traveling time or save time that’s why we develop such algorithms or such ways.
As I believe computer science is maths in electronic and digital form so we have always tried to find the most efficient ways to solve the problem, so as always we discussed algorithms in the previous articles we are going to discuss some below,
Bellman-Ford Algorithm
One of the first algorithms which fascinated me was the Bellman-Ford, Richard Bellman and Lester R. Ford designed this algorithm, and it is one of the most taught algorithms, in Dynamic Programming lectures, it uses the principle of? optimality and edge relaxation,?
Principle of Optimality: The principle of optimality is the basic principle of dynamic programming, which was developed by Richard Bellman: that an optimal path has the property that whatever the initial conditions and control variables (choices) over some initial period, the control (or decision variables) chosen over the remaining period must be optimal for the remaining problem, with the state resulting from the early decisions taken to be the initial condition.
Citation: Moffatt, Mike. "Principle of Optimality." ThoughtCo, Aug. 27, 2020, thoughtco.com/principle-of-optimality-definition-1147078.
The Bellman-Ford can handle negative edges, but it's slower than Dijkstra.
Here is the pseudocode for the Bellman-Ford algorithm,
In this pseudocode, Graph represents the graph with vertices and edges, the source is the source vertex, the distance is an array to store the shortest distances from the source vertex to each vertex, and the predecessor is an array to store the predecessors of each vertex in the shortest paths.
The algorithm consists of three steps:
Initialization: Set the distance of the source vertex to 0 and initialize the distance of all other vertices to infinity.
Relaxation: Iterate |V|-1 times and update the distance values if a shorter path is found.
Check for negative-weight cycles: If there is any improvement in the distances in the previous step, it indicates the presence of a negative-weight cycle.
Dijkstra’s Algorithm
Dijkstra’s algorithm is another algorithm for finding the? Shortest Path between nodes in a graph, it works efficiently on graphs with non-negative edges and weights. It was developed by Dutch computer scientist Edsger Dijkstra in 1956.
The explanation:
Suppose there is a graph that has nodes A, B, D, E, F, and C, and all the paths in the graph are weighted,
Like A to B, it is 2,
A to D it is 8,
B to D it is 5,?
B to E it is 6,
D to E it is 3,?
D to F it is 2,?
F to E it is 1,?
F to C it is 3
And we have to reach from A to C by taking the shortest path possible, so currently the distance at point A is 0,?
It has two options either go A to B, or A to D, but A to B is small its weight is 2, so it will move to B, and update the distance to 2,?
similarly, it would make a choice between D and E at B, and would go down the path which heads towards D as it is the shortest,
And will do the same for all other nodes and would eventually reach point C, with the total and shortest distance of 12,?
Use of Shortest Path Algorithms in real life
And many more,
There are few other algorithms for the shortest paths and many ways to implement these but these two are most efficient and widely discussed.
Nowadays I am heavily involved in AI and Deep Learning surely in the future we will see some articles on topics in the academic field of AI, Deep Learning, and Machine Learning.