Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights
Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
It uses a greedy approach with a priority queue — always expanding the vertex with the smallest known distance.
How It Works
Initialize `dist[source] = 0` and `dist[v] = ∞` for all other vertices.
Maintain a min-priority queue.
At each step, extract the vertex `u` with minimum distance, then **relax** all outgoing edges: if `dist[u] + w(u,v) < dist[v]`, update `dist[v]` and re-insert `v` into the priority queue.
Repeat until the queue is empty.
The final `dist` array contains shortest distances from the source.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Time (binary heap PQ) | O((V + E) log V) | O(V) |
| Time (Fibonacci heap) | O(E + V log V) | O(V) |
| Relax edge | O(log V) | O(1) |
| Extract minimum | O(log V) | O(1) |
| Works with negative weights? | No (use Bellman-Ford) | — |
Best Use Cases
- GPS navigation — shortest driving route between cities
- Network routing protocols (OSPF uses Dijkstra)
- Game AI pathfinding on weighted tile maps
- Social network — finding degrees of separation
- Airline route planning with minimum cost
Worked Example
Dijkstra from S on the weighted graph S→A→C→E→T
Input: S→A(2), S→B(4), A→C(3), A→D(7), B→D(1), C→E(2), D→E(3), D→T(6), E→T(1)- 1 Initialize dist[S]=0, all others ∞; extract S first.
- 2 Relax S's edges: A becomes 2, B becomes 4.
- 3 Extract A (2): C becomes 2+3=5; D would be 2+7=9 but is later improved.
- 4 Extract B (4): D improves to 4+1=5.
- 5 Extract C (5) and then D (5): E improves to 5+2=7 via C; D→E gives 5+3=8 (worse).
- 6 Extract E (7): T improves to 7+1=8; the final distances are S=0, A=2, B=4, C=5, D=5, E=7, T=8.
Pseudocode
function Dijkstra(graph, start):
dist[start] = 0
dist[v] = ∞ for all other v
pq = MinPQ(); pq.insert(start, 0)
while pq not empty:
u = pq.extractMin()
for each edge (u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pq.decreaseKey(v, dist[v])
return dist BFS — Breadth-First Search
Queue
Distances
| Node | Dist | Parent |
|---|
Result Order
SCC Groups
Distance Matrix
Select an algorithm and press Play to begin.