## Dijkstra's Shortest Path Algorithm
### The Core Idea
Dijkstra's algorithm finds the shortest path from a single source node to all other nodes in a weighted graph with **non-negative edge weights**. It's a greedy algorithm — at each step, it picks the unvisited node with the smallest known distance and locks it in.
### How It Works (Step by Step)
1. **Initialize**: Set distance to source = 0, all others = ∞. Mark all nodes as unvisited. Create a priority queue (min-heap).
2. **Pick the closest unvisited node**: Extract the node with the smallest distance from the priority queue.
3. **Relax its neighbors**: For each neighbor, calculate `new_dist = current_dist + edge_weight`. If `new_dist < neighbor's current distance`, update it.
4. **Mark as visited**: Once a node is processed, its shortest distance is finalized.
5. **Repeat** until all reachable nodes are visited or the priority queue is empty.
### Example
Consider this graph:
```
A --1-- B
| |
4 2
| |
C --5-- D --3-- E
```
**Source: A**
| Step | Visit | Distances: A, B, C, D, E |
|------|-------|--------------------------|
| 0 | — | 0, ∞, ∞, ∞, ∞ |
| 1 | A | 0, 1, 4, ∞, ∞ |
| 2 | B | 0, 1, 4, 3, ∞ |
| 3 | D | 0, 1, 4, 3, 6 |
| 4 | C | 0, 1, 4, 3, 6 |
| 5 | E | 0, 1, 4, 3, 6 |
Shortest paths from A: B=1, D=3 (A→B→D), C=4, E=6 (A→B→D→E).
### Time Complexity
- **With a min-heap (binary)**: O((V + E) log V) — this is the standard implementation
- **With a Fibonacci heap**: O(V log V + E) — theoretically better, rarely used in practice
- **With a simple array**: O(V²) — fine for dense graphs where E ≈ V²
### When to Use It (and When Not To)
| Scenario | Use Dijkstra? | Better Alternative |
|----------|--------------|-------------------|
| Non-negative weights, single source | ✅ Yes | — |
| Negative edge weights | ❌ No | Bellman-Ford O(VE) |
| Unweighted graph | Overkill | BFS O(V + E) |
| All-pairs shortest paths | Possible but slow | Floyd-Warshall O(V³) |
| Sparse graph with negative weights | ❌ No | SPFA (queue-optimized Bellman-Ford) |
### Key Gotcha
Dijkstra fails with negative weights because once a node is "visited," its distance is final. A negative edge discovered later could provide a shorter path, but the algorithm won't revisit it. This isn't just a theoretical concern — it produces wrong answers.
## Dijkstra's Algorithm: Finding the Shortest Path
### What Is It?
Dijkstra's algorithm is one of the most famous algorithms in computer science. Named after Edsger Dijkstra (1959), it solves the **single-source shortest path problem** for graphs with non-negative weights.
Think of it like this: imagine you're in a city and want to find the fastest driving route to every other location. Dijkstra's algorithm systematically explores outward from your starting point, always choosing the next closest location first.
### Step-by-Step Process
1. **Set up a distance table**: Assign distance 0 to your starting node and infinity (∞) to everything else.
2. **Use a priority queue**: Insert your start node. The queue always gives you the node with the smallest current distance.
3. **Process the closest node**: Take the node with the smallest distance out of the queue.
4. **Check all its neighbors**: For each neighboring node, see if going through the current node gives a shorter path. If yes, update the distance and add it to the queue.
5. **Repeat until done**: Keep processing nodes until the queue is empty.
### Walkthrough Example
Let's trace through a small graph:
```
A → B (weight 1)
A → C (weight 4)
B → C (weight 2)
B → D (weight 6)
C → D (weight 3)
```
Starting from **A**:
- **Start**: distances = {A: 0, B: ∞, C: ∞, D: ∞}
- **Process A**: Update B to 1, C to 4 → {A: 0, B: 1, C: 4, D: ∞}
- **Process B** (dist=1): Update C to min(4, 1+2=3) → 3. Update D to 1+6=7 → {A: 0, B: 1, C: 3, D: 7}
- **Process C** (dist=3): Update D to min(7, 3+3=6) → 6 → {A: 0, B: 1, C: 3, D: 6}
- **Process D** (dist=6): No updates needed.
**Result**: Shortest path from A to D = 6 (A → B → C → D)
### Time Complexity
The time complexity depends on your data structure:
| Implementation | Time Complexity | Best For |
|---------------|----------------|----------|
| Array/List | O(V²) | Dense graphs |
| Binary Heap | O((V + E) log V) | Most practical cases |
| Fibonacci Heap | O(V log V + E) | Theoretical optimization |
Where V = number of vertices and E = number of edges.
### When Should You Use Dijkstra's?
**Use it when:**
- All edge weights are non-negative
- You need shortest path from one source to all (or one specific) destination(s)
- The graph is reasonably sized
**Use something else when:**
- **Negative weights exist** → Use Bellman-Ford instead
- **Graph is unweighted** → BFS is simpler and equally effective
- **You need all pairs shortest paths** → Consider Floyd-Warshall
- **Very large graphs with heuristic available** → A* search is faster for point-to-point queries
### Common Mistakes to Avoid
1. **Using Dijkstra's with negative edges** — it won't work correctly
2. **Forgetting to use a visited set** — you'll process nodes multiple times
3. **Not understanding lazy deletion** — in practice, you may add duplicate entries to the priority queue; just skip nodes that have already been finalized