0 | 1 | 2 | 3 | |
---|---|---|---|---|
0 |
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.
The steps of dijkstra's algorithm are simple: