🛤️ Dijkstra's Algorithm

The GPS Navigation Analogy

When you ask GPS for directions:

1. It knows all roads and their travel times
2. It finds the lowest-cost route, not just the shortest distance
3. It considers WEIGHTS (time, not just number of turns)

Dijkstra's algorithm is like GPS - it finds the shortest weighted path from a starting point to all other nodes.

Why Not Just Use BFS?

BFS finds shortest path by number of edges, not by weight:

Path A → B → C: 2 edges, but total weight = 100
Path A → D → E → C: 3 edges, but total weight = 10

BFS picks A→B→C (fewer edges) ❌
Dijkstra picks A→D→E→C (lower weight) ✓

Dijkstra cares about total cost, not edge count.

How Dijkstra Works

The Core Idea

Start at source. Repeatedly expand the node with the smallest known distance. Update neighbors if you find a shorter path.

Step-by-Step Walkthrough

Graph:
    A --1-- B --2-- E
    |       |
    4       1
    |       |
    C --3-- D

Find shortest paths from A:

Initial state:

Distances: A=0, B=∞, C=∞, D=∞, E=∞
Visited: {}

Step 1: Process A (distance 0, smallest unvisited)

Check A's neighbors:
  B: 0 + 1 = 1 < ∞, update B = 1
  C: 0 + 4 = 4 < ∞, update C = 4

Distances: A=0, B=1, C=4, D=∞, E=∞
Visited: {A}

Step 2: Process B (distance 1, smallest unvisited)

Check B's neighbors:
  D: 1 + 1 = 2 < ∞, update D = 2
  E: 1 + 2 = 3 < ∞, update E = 3

Distances: A=0, B=1, C=4, D=2, E=3
Visited: {A, B}

Step 3: Process D (distance 2, smallest unvisited)

Check D's neighbors:
  C: 2 + 3 = 5 > 4, no update (existing path better)

Distances: A=0, B=1, C=4, D=2, E=3
Visited: {A, B, D}

Step 4: Process E (distance 3)

No unvisited neighbors.
Visited: {A, B, D, E}

Step 5: Process C (distance 4)

All neighbors visited.
Visited: {A, B, C, D, E}

Final shortest distances from A:

A→A: 0
A→B: 1
A→C: 4
A→D: 2 (via B)
A→E: 3 (via B)

The Priority Queue

How do we repeatedly pick the smallest unvisited node efficiently?

Use a min-heap (priority queue)!

Priority queue operations:
  - Insert node with distance: O(log n)
  - Extract minimum: O(log n)

Total: O((V + E) log V)

Without priority queue: O(V²) checking all vertices each time.

Reconstructing the Path

Dijkstra gives distances, but what about the actual path?

Track predecessors:

When updating a distance:
  predecessor[neighbor] = current_node

After algorithm:
  E's predecessor = B
  B's predecessor = A

Path A→E: Trace back: E←B←A, reverse: A→B→E

When Dijkstra Works

Requirements

1. Non-negative weights - Dijkstra fails with negative edges!
2. Weighted graph - For unweighted, use BFS instead

Why No Negative Weights?

    A --1-- B
    |       |
   -5       2
    |       |
    C ------+

From A:
  Dijkstra visits B (dist 1), marks it done
  But A→C→B = -5 + 2 = -3 is shorter!
  Too late - B is already "done"

For negative weights, use Bellman-Ford algorithm.

Dijkstra vs Other Algorithms

Real-World Applications

1. GPS Navigation

Find a low-time route considering road speeds and traffic.

2. Network Routing

Internet packets find paths with lowest latency.

3. Flight Planning

Find cheapest or shortest flights between cities.

4. Social Networks

Find degrees of separation with weighted connections.

Common Optimizations

1. Stop Early

If you just need the path to one target, you can stop when you visit it.

2. Bidirectional Dijkstra

Run from both source and target, meet in the middle. ~2x faster.

3. A* (A-Star)

Add heuristic estimate to guide search toward goal. Much faster for specific targets.

A* priority = distance_so_far + estimated_remaining

Dijkstra explores in circles
A* explores toward the goal

Common Mistakes

1. Using with Negative Weights

Dijkstra gives wrong answers! Use Bellman-Ford instead.

2. Forgetting the Priority Queue

Without it, you might process nodes in wrong order.

3. Processing Visited Nodes

Once a node is visited with shortest distance, don't process again!

4. Not Initializing Distances to Infinity

All non-source nodes start at ∞ distance.

FAQ

Q: Why is it called "greedy"?

Dijkstra repeatedly picks the node with the smallest known distance - a locally optimal choice that (with non-negative weights) leads to the globally optimal solution.

Q: Can Dijkstra find the shortest path between all pairs?

Run Dijkstra from each node, but Floyd-Warshall is often better for all-pairs.

Q: What if there are multiple shortest paths?

Dijkstra finds one valid shortest path. Modify to track all predecessors for all paths.

Q: What's the difference from BFS?

BFS: all edges have weight 1, uses regular queue. Dijkstra: edges have different weights, uses priority queue.

Summary

Dijkstra's algorithm finds the shortest path in weighted graphs by repeatedly expanding the closest unvisited node.

Key Takeaways:

• Greedy: process the smallest-distance node next
• Uses priority queue (min-heap) for efficiency
• O((V + E) log V) with priority queue
• Requires non-negative weights
• Track predecessors to reconstruct path
• Foundation for GPS, routing, and more

Dijkstra is a common choice for weighted shortest paths.