Dijkstra's Algorithm Pathfinding

Speed:

SlowFast

Cell weights are displayed as numbers (1-3). Higher numbers = higher cost to traverse.

Start

End

Wall

Visited

Current

Path

Weight

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O((V + E) log V) with binary heap priority queue

Space Complexity: O(V) for distances and priority queue

Optimal: Yes - guarantees shortest path for weighted graphs

Complete: Yes (will find solution if one exists)

How it works: Uses a priority queue to always explore the node with minimum distance next. Relaxes edges to find optimal paths.

Best for: Weighted graphs, GPS navigation, network routing protocols.

Key insight: Greedily selects minimum distance nodes, ensuring optimality through relaxation.

Implementation

function dijkstraPathfinding(grid, start, end) {
  const pq = new PriorityQueue();
  const visited = new Set();
  start.distance = 0;
  pq.enqueue(start, 0);
  while (!pq.isEmpty()) {
    const current = pq.dequeue();
    const key = `${current.row},${current.col}`;
    if (visited.has(key)) continue;
    visited.add(key);
    if (current === end) {
      return reconstructPath(end);
    }
    const neighbors = getNeighbors(current);
    for (const neighbor of neighbors) {
      if (!visited.has(`${neighbor.row},${neighbor.col}`) 
          && neighbor.type !== "wall") {
        const newDistance = current.distance + neighbor.weight;
        if (newDistance < neighbor.distance) {
          neighbor.distance = newDistance;
          neighbor.parent = current;
          pq.enqueue(neighbor, newDistance);
        }
      }
    }
  }
  return null;
}