Dijkstra’s algorithm is a popular method in computer science used to find the shortest path between nodes in a weighted graph. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956 and published three years later.
Here’s how the algorithm works:
Initialization: Start at the initial node and set its tentative distance from itself to 0, and all other nodes’ tentative distances to infinity. Create an empty set to keep track of visited nodes.
Selection of next node: Among the unvisited nodes, select the one with the smallest tentative distance.
Update distances: For the selected node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
Mark node as visited: Once all of the neighbors have been considered, mark the current node as visited and remove it from the unvisited set.
Termination condition: Repeat steps 2-4 until either the target node has been visited (in which case the shortest path has been found), or if the smallest tentative distance among the unvisited nodes is infinity (indicating that there is no connection between the initial node and remaining unvisited nodes).
Dijkstra’s algorithm is widely used in various applications including network routing protocols, GPS systems, and traffic modelling.
In this tutorial, I have utilised the Algorithm to find the shortest flight path between different countries.
#dijkstra #algorithm #python #flightpath
