Dijkstra's Shortest Path

📋 Quick Reference

Property	Value
Purpose	Shortest path from source to all vertices
Time Complexity	O((V + E) log V) with binary heap
Space Complexity	O(V)
Edge Weights	Non-negative only
Best For	GPS navigation, network routing, game pathfinding

One-liner: Greedy algorithm finding shortest paths by always extending the closest unvisited vertex.

🎮 Interactive Visualizer

Watch Dijkstra's algorithm find shortest paths step by step:

Dijkstra's Algorithm
Time: O((V+E) log V)Space: O(V)
1 / 25
Initialize: dist[0] = 0, all others = ∞. Add source to priority queue.
Real-world uses:GPS navigation, network routing, game pathfinding
⚠️ Limitation:No negative edge weights! Use Bellman-Ford instead
Distance Array (shortest paths from node 0)
Node 0(src)
0
Node 1
∞
Node 2
∞
Node 3
∞
Node 4
∞
Node 5
∞
Relaxation Formula
if dist[u] + weight(u,v) < dist[v] → update dist[v]
Priority Queue (min-heap)(node:distance)
0:0← MIN
Pseudocode
1dijkstra(graph, start):
2  dist[start]=0, dist[*]=∞
3  pq.add((0, start))
4  while pq not empty:
5    (d,u) = pq.extractMin()
6    if visited[u]: continue
7    visited[u] = true
8    for neighbor v of u:
9      if dist[u]+w < dist[v]:
10        dist[v] = dist[u]+w
11        pq.add((dist[v], v))
Variables
start
=0
dist[start]
=0
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Unvisited
Unvisited
Current
Current
Visited
Visited
P · [ ] · R
Loading visualizer...

Try these operations:

Select a source vertex
Watch distance relaxation as algorithm progresses
See the priority queue extract minimum distances
Observe the shortest path tree being built

🔧 Implementation

Basic Dijkstra (Priority Queue)

JAVA(39 lines)
Code
Loading syntax highlighter...

With Path Reconstruction

JAVA(59 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Implementation	Time	Space	Notes
Array (naive)	O(V²)	O(V)	Simple, good for dense graphs
Binary Heap	O((V+E) log V)	O(V)	Standard, good for sparse
Fibonacci Heap	O(V log V + E)	O(V)	Theoretical best

Step-by-Step Example

Graph:
    A --5-- B
    |       |
    2       3
    |       |
    C --1-- D

Starting from A:

Step 1: dist = {A:0, B:∞, C:∞, D:∞}
        Visit A, update neighbors
        dist = {A:0, B:5, C:2, D:∞}

Step 2: Extract min (C:2)
        Visit C, update neighbors
        dist = {A:0, B:5, C:2, D:3}

Step 3: Extract min (D:3)
        Visit D, update neighbors
        dist = {A:0, B:5, C:2, D:3}  (B via D = 3+3=6 > 5, no update)

Step 4: Extract min (B:5)
        All neighbors visited
        Final: {A:0, B:5, C:2, D:3}

✅ When to Use Dijkstra

Good Use Cases

GPS/Maps - shortest driving route
Network routing - packets through routers
Game AI - pathfinding for NPCs
Social networks - degrees of separation
Flight planning - cheapest route

Avoid When

Negative edge weights - use Bellman-Ford instead
Unweighted graphs - BFS is simpler and faster
All-pairs shortest paths - use Floyd-Warshall
Very dense graphs - O(V²) array version may be better

🔄 Algorithm Comparison

Algorithm	Use Case	Time	Handles Negatives?
BFS	Unweighted	O(V+E)	N/A
Dijkstra	Non-negative weights	O((V+E) log V)	No
Bellman-Ford	Any weights	O(VE)	Yes
Floyd-Warshall	All pairs	O(V³)	Yes
A*	Single target with heuristic	O((V+E) log V)	No

🧩 Common Variations

Early Termination (Single Target)

JAVA(18 lines)
Code
Loading syntax highlighter...

A* Enhancement (Heuristic)

JAVA(7 lines)
Code
Loading syntax highlighter...

K Shortest Paths

JAVA(7 lines)
Code
Loading syntax highlighter...

⚠️ Common Pitfalls

1. Negative Edge Weights

JAVA(7 lines)
Code
Loading syntax highlighter...

2. Not Skipping Processed Nodes

JAVA(12 lines)
Code
Loading syntax highlighter...

3. Integer Overflow

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Missing Nodes in Graph

JAVA(5 lines)
Code
Loading syntax highlighter...

🎤 Interview Tips

Q: Why doesn't Dijkstra work with negative weights?

"

Dijkstra relies on the greedy property: once a node is visited with distance d, no shorter path exists. Negative edges can create shorter paths through already-visited nodes, breaking this assumption.

Q: How does Dijkstra differ from BFS?

"

BFS treats all edges equally (unit weight), Dijkstra accounts for varying edge weights. BFS uses a simple queue; Dijkstra uses a priority queue ordered by distance.

Q: What's the time complexity with different data structures?

"

With array: O(V²) - linear search for minimum. With binary heap: O((V+E) log V) - logarithmic extract-min. With Fibonacci heap: O(V log V + E) - theoretical best.

Q: How would you find the path, not just distance?

"

Track predecessors in a parent map. When updating dist[v], also set parent[v] = u. Reconstruct path by following parent pointers from target to source.

Previous: Part 11: Graph Traversal (DFS & BFS)

Next: Part 13: Dynamic Programming

Visualizer: Dijkstra from @tomaszjarosz/react-visualizers