Dijkstra's Algorithm
A graph algorithm that finds shortest paths from one node to all others with non-negative edge weights.
Definition
Dijkstra's algorithm computes the shortest path from a source node to every other node in a weighted graph with non-negative edge weights. It repeatedly finalizes the nearest unvisited node and relaxes the distances to its neighbors.
It fails when edges can be negative, because a later cheap edge could improve an already-finalized node; the Bellman-Ford algorithm handles that case at higher cost. The A-star algorithm extends Dijkstra with a heuristic to reach a goal faster when one exists.
The algorithm's efficiency depends on the priority queue used to select the next-nearest node; a binary heap gives near-linear-logarithmic time, and more advanced heaps improve the bound further. Its assumption of non-negative weights is essential and easy to overlook. When a heuristic estimate of remaining distance is available, the A-star variant uses it to explore fewer nodes, which is why navigation systems favor A-star over plain Dijkstra.
How it proceeds
- Set the source distance to zero, all others to infinity.
- Pick the unvisited node with the smallest tentative distance.
- Update its neighbors' distances if a shorter path is found.
- Repeat until all nodes are finalized.
Why it matters
Dijkstra is the standard shortest-path algorithm, underlying routing, navigation, and network analysis. It is a greedy algorithm that is provably optimal here because non-negative weights guarantee that a finalized node's distance never improves later. A priority queue gives it O(E + V log V) time.
Fusion connection
Shortest-path reasoning appears in optimizing routing of cooling and diagnostic pathways through the dense mechanical layout of a fusion machine.