Find Shortest Path

find-shortest-path

When to Use

• Finding shortest/optimal path between two points
• Maze solving
• Game AI movement
• Route planning and navigation
• Graph traversal (BFS, DFS, A*)
• State-space search problems
• Puzzle solving (15-puzzle, Rubik's cube)

When NOT to Use

• Simple iteration over all nodes (just use a loop)
• When there's no clear goal state
• Infinite graphs without good heuristics

The Pattern

Use A* search with a problem abstraction that separates:

• State representation
• Goal testing
• Action generation
• Cost function
• Heuristic (optional, for A*)

from heapq import heappush, heappop

def astar_search(problem, h=lambda n: 0):
    """A* search: expand nodes with minimum f(n) = g(n) + h(n)."""
    start = problem.initial
    frontier = [(h(start), 0, start, [])]  # (f, g, state, path)
    reached = {start: 0}

    while frontier:
        f, g, state, path = heappop(frontier)

        if problem.is_goal(state):
            return path + [state]

        for action, next_state, cost in problem.actions(state):
            new_g = g + cost
            if next_state not in reached or new_g < reached[next_state]:
                reached[next_state] = new_g
                new_f = new_g + h(next_state)
                heappush(frontier, (new_f, new_g, next_state, path + [state]))

    return None  # No path found

Example (from pytudes AdventUtils.ipynb)

class GridProblem:
    """Find shortest path on a grid."""
    def __init__(self, grid, start, goal):
        self.grid, self.initial, self.goal = grid, start, goal

    def is_goal(self, state):
        return state == self.goal

    def actions(self, state):
        """Yield (action, next_state, cost) tuples."""
        for neighbor in self.grid.neighbors(state):
            yield (neighbor, neighbor, 1)

    def h(self, state):
        """Manhattan distance heuristic."""
        return abs(state[0] - self.goal[0]) + abs(state[1] - self.goal[1])

# Usage
problem = GridProblem(grid, start=(0, 0), goal=(10, 10))
path = astar_search(problem, h=problem.h)

Key Principles

1. Separate problem from algorithm: Problem defines states/actions, algorithm searches
2. Priority queue: Always expand most promising node first
3. Reached set: Track best cost to each state to avoid cycles
4. Heuristic must not overestimate: h(n) <= actual cost for A* optimality
5. MRV heuristic: When branching, try most constrained option first