Visualize how we find the absolute shortest path in a weighted network using a greedy approach.
Graph Config
Search Speed
Search Statistics
Visited Nodes0
Total Nodes0
Weighted Exploration Map
Ready
Click a node to set as Source point • Default is 'A'
Min Priority Queue
PQ is empty
Exploration Path
Dijkstra's always picks the node with the smallest tentative distance. It "relaxes" edges by checking if passing through the current node creates a shorter path to its neighbors.
Deconstructing Dijkstra's Algorithm
How a GPS finds the fastest route: a step-by-step guide to the shortest path.
Quick Context: What is Dijkstra's Algorithm?
Dijkstra's Algorithm is a classic method for finding the shortest path between a starting node and all other nodes in a weighted graph. It's the logic behind GPS navigation systems that find the quickest route from your home to a destination, considering traffic and road distances (weights). The algorithm is "greedy," meaning it always chooses the next-best move—the path with the lowest current cost.
The Core Idea: The Priority Queue and Tentative Distances
Dijkstra's works by maintaining a set of "tentative distances" for every node. Initially, the start node's distance is 0, and all others are infinity. The algorithm then systematically visits nodes, always picking the unvisited node with the smallest tentative distance.
Priority Queue (PQ): This is the key data structure. It stores nodes to be visited, prioritized by their tentative distance. The node with the smallest distance is always at the front, ready to be processed.
Visiting a Node: When a node is "visited," it's removed from the PQ. We then look at its neighbors.
Relaxing Edges: For each neighbor, we calculate a new potential distance: `(distance to current node) + (weight of edge to neighbor)`. If this new distance is shorter than the neighbor's current tentative distance, we update it. This is called "relaxing" the edge.
Guided Experiments with the Visualizer
Set the Source: Click on any node in the "Exploration Map" to set it as the starting point (Source). By default, it's 'A'.
Start and Step: Click "Start Solver". The source node is added to the Priority Queue (PQ) with a distance of 0. Now, click the "Step" button.
Observe the First Step: The source node is removed from the PQ (it's the "current" node, highlighted in yellow). Its neighbors are added to the PQ with their respective edge weights as their tentative distances. Notice the "Exploration Path" and "Min Priority Queue" panels update.
Continue Stepping: Click "Step" again. The algorithm now picks the node with the lowest distance from the PQ. It becomes the new "current" node. The process of checking its neighbors and "relaxing" edges repeats. Watch how the tentative distances in the PQ get updated if a shorter path is found.
Use Auto-Run: Reset the grid and click "Start Solver", then "Auto". Watch the algorithm run at full speed. The "Visited Nodes" count will increase until all reachable nodes have been finalized.
Change Topology: Use the "Network Topology" dropdown to select "Complex Mesh". This creates a graph with cycles. Run the algorithm again. Dijkstra's handles this perfectly, ensuring it never gets stuck in a loop and still finds the optimal path.
An Important Limitation
Standard Dijkstra's algorithm does not work correctly with graphs that have negative edge weights. Because it's a greedy algorithm, once a node is marked as "visited," its path is considered final. A negative edge encountered later could have created a shorter path, but Dijkstra's won't go back to check. For such cases, other algorithms like Bellman-Ford are used.
Key Takeaways
Greedy Choice: Always explores the most promising path first (the one with the lowest total weight so far).
Priority Queue is Essential: Efficiently finding the unvisited node with the minimum distance is crucial for performance.
Finalized Paths: Once a node is visited, its shortest path from the source is locked in and will not change.
Application: Perfect for network routing, GPS navigation, and any problem that can be modeled as finding the cheapest path in a graph with non-negative weights.
Cheat sheet
Dijkstra's Algorithm
Dijkstra's Algorithm is a classic method for finding the shortest path between a starting node and all other nodes in a weighted graph. It's the logic behind GPS navigation systems that find the quickest route from your home to a destination, considering traffic and road distances (weights). The algorithm is "greedy," meaning it always chooses the next-best move—the path with the lowest current cost.