Pathfinding Visualizer

1. Dijkstra's Algorithm

Explores nodes in order of their distance from the start using a priority queue. Guarantees the shortest path in weighted graphs with non-negative edge weights.

function* dijkstra(grid: Cell[][], start: [number,number], end: [number,number]) {
  const pq: [number, number, number][] = [[0, sr, sc]];
  const dist = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
  const prev = new Map<string, string | null>();
  const visited = new Set<string>();
  dist[sr][sc] = 0;
  prev.set(`${sr},${sc}`, null);
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, r, c] = pq.shift()!;
    const key = `${r},${c}`;
    if (visited.has(key)) continue;
    visited.add(key);
    // yield visited/frontier state...
    // relax neighbors and push into pq
  }
}

2. A* Algorithm

A* improves on Dijkstra by adding a heuristic h(n) — the estimated distance to the goal. f(n) = g(n) + h(n), where g(n) is the path cost so far. This guides the search toward the goal and usually visits far fewer nodes.

function heuristic(r: number, c: number, er: number, ec: number): number {
  return Math.abs(r - er) + Math.abs(c - ec); // Manhattan distance
}
// f = g + h
const f = tentativeG + heuristic(nr, nc, er, ec);

3. BFS vs DFS

BFS uses a queue (FIFO) to explore the graph level by level, guaranteeing the shortest path in unweighted grids. DFS uses a stack (LIFO), going as deep as possible before backtracking; it does not guarantee the shortest path but produces a very different exploration pattern.

// BFS: Queue (FIFO)
const queue: [number, number][] = [[sr, sc]];
const [r, c] = queue.shift()!;

// DFS: Stack (LIFO)
const stack: [number, number][] = [[sr, sc]];
const [r, c] = stack.pop()!;

4. Path Reconstruction

All algorithms maintain a prev map where each cell points to the cell that discovered it. To reconstruct the path, we walk backwards from the end node to the start node using this map.

function reconstructPath(
  prev: Map<string, string | null>,
  start: [number, number],
  end: [number, number],
): string[] {
  const path: string[] = [];
  let current: string | null = `${end[0]},${end[1]}`;
  const startKey = `${start[0]},${start[1]}`;
  while (current !== null) {
    path.unshift(current);
    current = prev.get(current) ?? null;
  }
  if (path[0] !== startKey) return [];
  return path;
}