Pathfinding Algorithm
Dijkstra's Algorithm
“The Serious Professional”
History
Edsger W. Dijkstra invented this algorithm in 1956 over a cup of coffee. He wanted to demonstrate the power of the new ARMAC computer but needed a problem that non-mathematicians could understand. He chose "finding the shortest route between two cities in the Netherlands."
Dijkstra was a stickler for elegance and correctness. His algorithm reflects that personality. It doesn't guess, and it doesn't take shortcuts. It simply calculates the mathematically optimal path with ruthless efficiency.
How It Works
Dijkstra's Algorithm is essentially BFS with a brain for costs. It accounts for "weighted" edges (like traffic, terrain cost, or toll roads).
The Algorithm Step-by-Step
- Initialize: Set distance to start as 0 and all other nodes to Infinity.
- Priority Queue: Put the start node in a min-priority queue.
- Extract Min: Grab the node with the currently shortest known distance.
- Relaxation: Check all neighbors. If the distance to the current node + the edge weight is less than the neighbor's known distance, update the neighbor's distance and parent.
- Repeat: Keep going until the destination is finalized.
The "Relaxation" Concept
It sounds like a spa treatment, but in graph theory, "relaxing" an edge means checking if we found a shortcut. If we found a faster way to get to Node B via Node A, we update our records.
Greedy but Correct
It always processes the "closest" unprocessed node next. This ensures that once a node is visited, we have mathematically proven the shortest path to it.
The log V comes from the Priority Queue operations. It's slower than BFS per step, but much more powerful because it handles weights.
We need to store the distance estimates for every node and the priority queue itself.
The core data structure powering Dijkstra's Algorithm.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1import heapq23def dijkstra(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:4 """Find shortest path in weighted grid using Dijkstra's algorithm.5 Cell values represent movement cost (0 = blocked)."""6 rows, cols = len(grid), len(grid[0])7 distances = {start: 0}8 parents = {start: None}9 heap = [(0, start)]10 visited = set()11 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]1213 while heap:14 dist, (row, col) = heapq.heappop(heap)1516 if (row, col) in visited:17 continue18 visited.add((row, col))1920 if (row, col) == end:21 # Reconstruct path22 path = []23 curr = end24 while curr:25 path.append(curr)26 curr = parents[curr]27 return path[::-1]2829 for dr, dc in directions:30 nr, nc = row + dr, col + dc3132 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > 0:33 new_dist = dist + grid[nr][nc]3435 if (nr, nc) not in distances or new_dist < distances[(nr, nc)]:36 distances[(nr, nc)] = new_dist37 parents[(nr, nc)] = (row, col)38 heapq.heappush(heap, (new_dist, (nr, nc)))3940 return NoneReal World Use Cases
- 1Google Maps / GPS Navigation
- 2Network Routing Protocols (OSPF)
- 3Logistics and Supply Chain optimization
- 4Airline flight planning
- 5Social Network modeling
- 6Telephone network routing
Key Insights
- It handles weighted graphs (mud costs more movement than road).
- It guarantees the shortest path for non-negative weights.
- It is the grandfather of A*.
- It calculates the shortest path from the start to *all* other nodes.
- It fails if negative edge weights exist (you need Bellman-Ford for that).
When to Use
Use Dijkstra when movement costs vary (e.g., a game with swamps and roads) and you need the absolute optimal path. It is the industry standard for established routing.
When NOT to Use
Avoid Dijkstra if all weights are equal (BFS is faster) or if you need to find the path very quickly in a massive map (use A*).