Dijkstra's Algorithm

Basic Information

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Algorithm

1. Mark all nodes as unvisited and create an unvisited set.
2. Set the distance from the start to zero for the starting node and infinity for others. The distance of a node is the shortest path from the start to that node. Set the starting node as current.
3. For the current node, update the distances of its unvisited neighbors. If the new distance is smaller, update it.
4. Once all unvisited neighbors are considered, mark the current node as visited and remove it from the unvisited set. The recorded distance is final.
5. Review the unvisited nodes. Select the one with the smallest distance as the new current node and repeat from step 3. If a node's distance is infinity, it's not reachable. The algorithm finishes when there are no reachable unvisited nodes or the target node becomes the current node.
6. After the loop, the shortest path can be found by starting from the target node and choosing its neighbor with the shortest distance, tracing back to the start. If the target node's distance is infinite, no path exists.
7. See more about the Pseudocode

Graph Representation