Dijkstra's algorithm is a popular graph traversal algorithm used to find the shortest path between nodes in a graph with non-negative edge weights. It guarantees the shortest path from a starting node to all other nodes in the graph.
function Dijkstra(graph, start):
distances := map of all nodes with infinity value
distances[start] := 0
visited := empty set
unvisited := set of all nodes
while unvisited is not empty:
current := node in unvisited with smallest distance
for neighbor in neighbors of current:
tentativeDistance := distances[current] + distance(current, neighbor)
if tentativeDistance < distances[neighbor]:
distances[neighbor] := tentativeDistance
visited.add(current)
unvisited.remove(current)
return distances
Dijkstra's algorithm starts by assigning the starting node a distance of zero and all other nodes a distance of infinity. It then iteratively selects the node with the smallest tentative distance and explores its neighbors. If the tentative distance to a neighbor through the current node is smaller than its current distance, the algorithm updates the neighbor's distance.
The algorithm continues until all nodes have been visited or the smallest tentative distance among the unvisited nodes is infinity. At the end of the algorithm, the distances map holds the shortest distances from the starting node to all other nodes in the graph.