Dijkstra's & A* Pathfinding: Heuristics & Graph Traversal

Pathfinding is central to computer science - powering GPS navigation systems, network packet routing, and video game AI. While Dijkstra’s algorithm guarantees finding the shortest path by exploring all directions uniformly, the A Search algorithm* uses a heuristic function to steer exploration directly toward the destination.

1. Summary & Key Takeaways

• Dijkstra’s Algorithm: Evaluates nodes based strictly on path cost from the start: $f(n) = g(n)$
• $A^*$ Search Algorithm: Adds an admissible heuristic $h(n)$ estimating remaining distance to the goal: $f(n) = g(n) + h(n)$
• Manhattan Distance Heuristic: For grid graphs with 4-directional movement: $h(n) = |x_1 - x_2| + |y_1 - y_2|$
• Efficiency Boost: $A^*$ evaluates significantly fewer nodes than Dijkstra while still guaranteeing the shortest optimal path if the heuristic never overestimates the true cost ($h(n) \le h^*(n)$).

2. Interactive Pathfinding Playground

Use the interactive 2D grid below to place wall barriers. Switch between $A^*$ Search and Dijkstra to observe how heuristic guidance drastically reduces the number of visited nodes!

# Dijkstra & A* Search Pathfinding in Python
import heapq

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan distance

def a_star_search(start, goal, grid):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}
    
    while open_set:
        current = heapq.heappop(open_set)[1]
        if current == goal:
            return reconstruct_path(came_from, current)
        
        for neighbor in get_neighbors(current, grid):
            tentative_g = g_score[current] + 1
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, neighbor))

3. Mathematical Foundations

The core score $f(n)$ assigned to each node during priority queue exploration determines traversal order:

1. Dijkstra ($f(n) = g(n)$)

Explores nodes in concentric circles outward from the origin regardless of target location.

2. $A^*$ ($f(n) = g(n) + h(n)$)

Directs exploration toward the goal. For 4-way grid movement, Manhattan distance provides an admissible, consistent heuristic:

$h(n) = |x_{\text{current}} - x_{\text{target}}| + |y_{\text{current}} - y_{\text{target}}|$

4. Algorithm Comparison Matrix