Dijkstra's Shortest Path Visualizer
Watch how Dijkstra's algorithm finds the absolute shortest path between nodes in a weighted network step-by-step. Select nodes, tune playback speed, and trace variable states in real time.
Graph Controls
Algorithm Distance Table
| Node | Distance | Prev Node |
|---|---|---|
| A | ∞ | - |
| B | ∞ | - |
| C | ∞ | - |
| D | ∞ | - |
| E | ∞ | - |
| F | ∞ | - |
How Dijkstra’s Algorithm Works (Line-by-Line Guide)
Dijkstra’s Algorithm is a fundamental graph traversal algorithm developed by computer scientist Edsger W. Dijkstra in 1956. Its primary goal is to find the absolute shortest path between a starting source node and all other nodes (or a target end node) in a graph with non-negative edge weights.
The Step-by-Step Logic & Edge Relaxation
The algorithm achieves this shortest-path search by maintaining a list of tentative distances from the source to every other node in the graph, adjusting them incrementally as it discovers more optimal paths. This process of updating distances is known as edge relaxation.
- Initialization: Set the distance to the start node to
0, and the distance to all other nodes toInfinity. Set the predecessor of all nodes to null/empty. Mark all nodes as unvisited. - Priority Queue Selection: Pick the unvisited node with the smallest tentative distance. At the beginning, this will always be the start node. This selected node is marked as the current node being processed.
- Neighbor Assessment & Relaxation: For the current node, look at all of its unvisited neighbors. Calculate their cumulative distance from the start node through the current node. If this new cumulative distance is smaller than the neighbor's current recorded distance, update the neighbor's distance to this new lower value, and record the current node as its predecessor.
- Termination or Loop: Once all neighbors of the current node have been evaluated, mark the current node as visited (fully processed). A visited node will never be checked again. Repeat steps 2 and 3 until the destination end node is marked visited or all reachable nodes are processed.
- Reconstruct Path: To trace the final path, backtrack from the destination node to the start node using the recorded predecessor/previous node associations.
The Critical Role of Data Structures
To implement Dijkstra’s algorithm efficiently in code, a Min-Priority Queue (often backed by a binary heap) is used. Rather than scanning the entire list of nodes to find the node with the minimum distance at each step (which takes \(O(V)\) time), the min-priority queue allows retrieving the node with the absolute smallest distance in \(O(\log V)\) time. This optimizes the traversal significantly in dense graph structures.