Dijkstra’s Algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest path in a network of nodes in a graph (abstract data type). The original Dijkstra’s algorithm found the shortest path between two nodes but now many variants exist. A more common variant fixes a single node as a source node and finds the shortest path from the source to all other nodes in the graph. It thus produces a shortest path-tree. It can also be used to find the shortest node from a source node to a destination node; this is achieved by stopping the algorithm once the destination node is reached. For example, if the nodes of the graph were to represent cities then Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.

Let the initial starting node be called the initial node. Dijkstra’s algorithm works by initially assigning the initial node a zero value and an infinity value to all other nodes. It also creates an unvisited set and assigns it all the unvisited nodes which are initially all the nodes except initial node. First assign all the neighbors of initial node their tentative distances and then compare their values from their initial values and replace if that value is smaller. In this case the initial value was infinity so it will be replaced. Set the initial node as visited and check the neighbors of the initial node and repeat the above step. In the end the final destination node having the smallest value is selected and its path is made from the initial node.

This algorithms is widely used in network routing protocols, most notable being IS-IS and OSPF (Open Shortest Path First). It is also employed in other algorithms like Johnson’s as a subroutine.