Dijkstra’s Algorithm is a fundamental method in computer science for finding the shortest paths between nodes in a weighted graph. It was introduced by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
How It Works:
- Initialization: Assign a tentative distance value to every node: set the initial node’s distance to zero and all other nodes’ distances to infinity.
- Visit Nodes: Select the unvisited node with the smallest tentative distance.
- Update Distances: For each unvisited neighbor of the current node, calculate the tentative distance from the start node. If this distance is less than the current assigned value, update it.
- Mark as Visited: Once all neighbors have been considered, mark the current node as visited. A visited node will not be checked again.
- Repeat: Continue the process until all nodes have been visited.