Dijkstra's algorithm

Description

Dijkstra's algorithm is a graph search algorithm which solves the single-source shortest path problem and belongs to the Greedy technique. The algorithm is developed by the Dutch computer scientist Edsger W. Dijkstra (1930 – 2002) in 1956. Dijkstra’s algorithm exists in many variants. The original variant found the shortest path between two nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path algorithm is widely used in network routing protocols and as a subroutine in other graph algorithms.

Algorithm

The steps of dijkstra's algorithm are simple:

1. Take the starting node
2. Compute the distances to every other connected node (just follow the edges from the starting node)
3. Take the smallest edge, and follow it to a new node
4. Use the edges from the new node to update the table, and possibly create new/smaller paths to other nodes
5. Take the new smallest edge to a node that was not visited yet
6. Repeat from step 4