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