Skip to content

Latest commit

 

History

History

dijkstra_shortest_path

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 

Dijkstra's Shortest Path Algorithm

Finds the shortest path between nodes in a network. Starts with an initial node and will assign distance values that will be improved through each step. Start by assigning a distance value (zero for initial node, infinity for others), and create a set of unvisited nodes. For the current node, calculate all its neighbors and their tentative differences, compare that value with the assigned value, smaller one then gets assigned. After considering all neighbors of the current node, mark the node as visited and remove it from the unvisited set. If the destination node has been marked visited or if the smallest tentative distance among the nodes in the unvisited set is infinity (no connection between initial and remaining nodes), stop the algorithm. Otherwise, set the current node to a unvisited node with the smallest tentative distance, and repeat.