Dijkstra Shortest Path Simulation
Dijkstra's algorithm finds minimum-cost paths from a source node in weighted graphs with non-negative edge costs by greedily expanding the closest unvisited node and relaxing neighbor edges.
Interactive simulation
- Current node
- -
- Visited
- 0 / 6
- Max cost (F)
- 0
- Selected edge
- none
- Speed
- 1x
Legend
- Unvisited (∞ initially)
- Discovered / Frontier
- Active node being expanded
- Finalized shortest path
- Selected edge (click Block Edge)
- Blocked link
Event log
How to use this simulation
- Press Relax Next once to step through one edge relaxation at a time, or press Resume to animate continuously from the chosen Source Node.
- Click any edge line in the graph to select it, then press Block Edge to cut that link and watch shortest paths reroute.
- Use Step to advance one event, Slower (down to 0.25x) and Faster (up to 4x) to control animation speed, and Reset to restore all edges.
1. Greedy selection of the closest unvisited node
At each step, Dijkstra picks the unvisited node with the smallest tentative distance from the source. Because all edge weights are non-negative, once a node is chosen as the minimum among unvisited nodes, no shorter path to it can arrive later.
2. Edge relaxation
When expanding node u with cost dist[u], the algorithm checks each outgoing edge (u, v) of weight w. If dist[u] + w < dist[v], it updates dist[v] = dist[u] + w and records u as v's predecessor along the shortest tree.
3. Why non-negative weights are required
Dijkstra assumes adding another edge never decreases total path cost. If a graph has negative edge weights, an already-finalized node could later see a lower cost, requiring Bellman-Ford instead.
Algorithm properties
| Aspect | Detail | Why It Matters |
|---|---|---|
| Edge weight rule | Non-negative weights (w ≥ 0) | Preserves greedy optimality once a node is finalized |
| Relaxation condition | dist[u] + w < dist[v] | Updates neighbor cost only when a cheaper route is found |
| Time complexity | O((V + E) log V) with min-heap | Scales cleanly to sparse and dense graphs |
Key takeaways
- Always expand the unvisited node with the smallest current distance from the source.
- Relaxing an edge tests whether going through the current node improves a neighbor's cost.
- Blocking an edge forces remaining paths to use alternative routes or increases path cost.
Related topics
Go-Back-N
Sliding window ARQ with cumulative ACKs.
Selective Repeat
Sliding window ARQ with individual ACKs and buffering.
Bellman-Ford
Shortest paths with negative edge weights.
Coming soonA* Search
Heuristic-guided shortest path search.
Coming soon