Project: Pathfinding Visualizer (BFS & Dijkstra on a Grid)
In this project you’ll build the engine behind a pathfinding visualizer — the part that, given a grid with walls, finds the shortest route from a start cell to a target. A grid is just a graph in disguise: each open cell is a node, and adjacent cells are connected by edges. So the right tools are graph search: Breadth-First Search (BFS) when every step costs the same, and Dijkstra’s algorithm when steps have different costs. Read Breadth-First Search and Dijkstra’s Shortest Path for the underlying theory.
What you’ll build
Given a 2D grid where 0 is open and 1 is a wall, plus a start and target cell, return the length (or cost) of the shortest path, or -1 if the target is unreachable. We move in the four cardinal directions. This core function is what a UI would call on every frame to draw the path.
Part 1 — unweighted grids with BFS
When every move costs exactly one step, BFS is optimal: it explores the grid in expanding rings, so the first time it reaches the target, it has used the fewest steps possible. The key technique is processing the queue one level at a time — count how many cells are in the queue, drain exactly that many, then increment the step counter. Mark cells visited as you enqueue them (not when you dequeue) so the same cell never enters the queue twice.
#include <vector>
#include <queue>
#include <utility>
// grid: 0 = open, 1 = wall. Returns steps from start to target, or -1.
int shortestPath(const std::vector<std::vector<int>>& grid,
std::pair<int,int> start, std::pair<int,int> target) {
int rows = grid.size(), cols = grid[0].size();
std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
std::queue<std::pair<int,int>> q;
q.push(start);
visited[start.first][start.second] = true;
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
int steps = 0;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
auto [r, c] = q.front(); q.pop();
if (r == target.first && c == target.second) return steps;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !visited[nr][nc] && grid[nr][nc] == 0) {
visited[nr][nc] = true;
q.push({nr, nc});
}
}
}
steps++;
}
return -1;
}import java.util.*;
class GridPath {
// grid: 0 = open, 1 = wall. Returns steps from start to target, or -1.
static int shortestPath(int[][] grid, int[] start, int[] target) {
int rows = grid.length, cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> q = new ArrayDeque<>();
q.add(start);
visited[start[0]][start[1]] = true;
int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
int steps = 0;
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
if (r == target[0] && c == target[1]) return steps;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !visited[nr][nc] && grid[nr][nc] == 0) {
visited[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
steps++;
}
return -1;
}
}// grid: 0 = open, 1 = wall. Returns steps from start to target, or -1.
function shortestPath(grid, start, target) {
const rows = grid.length, cols = grid[0].length;
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
let queue = [start];
visited[start[0]][start[1]] = true;
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let steps = 0;
while (queue.length > 0) {
const next = [];
for (const [r, c] of queue) {
if (r === target[0] && c === target[1]) return steps;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
&& !visited[nr][nc] && grid[nr][nc] === 0) {
visited[nr][nc] = true;
next.push([nr, nc]);
}
}
}
queue = next;
steps++;
}
return -1;
}from collections import deque
# grid: 0 = open, 1 = wall. Returns steps from start to target, or -1.
def shortest_path(grid, start, target):
rows, cols = len(grid), len(grid[0])
visited = [[False] * cols for _ in range(rows)]
q = deque([start])
visited[start[0]][start[1]] = True
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
steps = 0
while q:
for _ in range(len(q)):
r, c = q.popleft()
if (r, c) == target:
return steps
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols \
and not visited[nr][nc] and grid[nr][nc] == 0:
visited[nr][nc] = True
q.append((nr, nc))
steps += 1
return -1Gotcha: BFS is only optimal when every edge has the same weight. The moment some cells are “slow” (mud, water), BFS can return a path that’s short in steps but expensive in cost. That’s where Dijkstra comes in.
Part 2 — weighted grids with Dijkstra
Now let cost[r][c] be the cost to step onto that cell. Dijkstra generalizes BFS by always expanding the cheapest-known cell next, using a min-priority queue keyed on distance. Keep a dist grid of best-known costs; when you pop a cell whose stored distance is worse than the best you’ve recorded, skip it (a stale duplicate). The first time you pop the target, its distance is final.
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
// cost[r][c] = cost to step onto that cell. Returns min cost, or -1.
int dijkstraGrid(const std::vector<std::vector<int>>& cost,
std::pair<int,int> start, std::pair<int,int> target) {
int rows = cost.size(), cols = cost[0].size();
std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, INT_MAX));
using State = std::tuple<int,int,int>; // (distance, row, col)
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
dist[start.first][start.second] = 0;
pq.push({0, start.first, start.second});
int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
while (!pq.empty()) {
auto [d, r, c] = pq.top(); pq.pop();
if (r == target.first && c == target.second) return d;
if (d > dist[r][c]) continue; // stale entry
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int nd = d + cost[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
pq.push({nd, nr, nc});
}
}
}
return -1;
}import java.util.*;
class GridDijkstra {
// cost[r][c] = cost to step onto that cell. Returns min cost, or -1.
static int dijkstra(int[][] cost, int[] start, int[] target) {
int rows = cost.length, cols = cost[0].length;
int[][] dist = new int[rows][cols];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
// entries: {distance, row, col}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
dist[start[0]][start[1]] = 0;
pq.add(new int[]{0, start[0], start[1]});
int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], r = top[1], c = top[2];
if (r == target[0] && c == target[1]) return d;
if (d > dist[r][c]) continue; // stale entry
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int nd = d + cost[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
pq.add(new int[]{nd, nr, nc});
}
}
}
return -1;
}
}class MinHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p][0] <= a[i][0]) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0];
const last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
let l = 2 * i + 1, r = 2 * i + 2, s = i;
if (l < a.length && a[l][0] < a[s][0]) s = l;
if (r < a.length && a[r][0] < a[s][0]) s = r;
if (s === i) break;
[a[s], a[i]] = [a[i], a[s]];
i = s;
}
}
return top;
}
}
// cost[r][c] = cost to step onto that cell. Returns min cost, or -1.
function dijkstraGrid(cost, start, target) {
const rows = cost.length, cols = cost[0].length;
const dist = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
const pq = new MinHeap(); // entries: [distance, row, col]
dist[start[0]][start[1]] = 0;
pq.push([0, start[0], start[1]]);
const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
while (pq.size > 0) {
const [d, r, c] = pq.pop();
if (r === target[0] && c === target[1]) return d;
if (d > dist[r][c]) continue; // stale entry
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
const nd = d + cost[nr][nc];
if (nd < dist[nr][nc]) {
dist[nr][nc] = nd;
pq.push([nd, nr, nc]);
}
}
}
return -1;
}import heapq
# cost[r][c] = cost to step onto that cell. Returns min cost, or -1.
def dijkstra_grid(cost, start, target):
rows, cols = len(cost), len(cost[0])
dist = [[float("inf")] * cols for _ in range(rows)]
dist[start[0]][start[1]] = 0
pq = [(0, start[0], start[1])] # (distance, row, col)
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while pq:
d, r, c = heapq.heappop(pq)
if (r, c) == target:
return d
if d > dist[r][c]:
continue # stale entry
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
nd = d + cost[nr][nc]
if nd < dist[nr][nc]:
dist[nr][nc] = nd
heapq.heappush(pq, (nd, nr, nc))
return -1Complexity
For a grid with V = rows × cols cells and at most 4V edges:
| Algorithm | Use when | Time | Space |
|---|---|---|---|
| BFS | all steps cost the same | O(V) | O(V) |
| Dijkstra | steps have different costs | O(V log V) | O(V) |
Going deeper: To draw the actual path (not just its length), store a
parentfor each cell as you discover it, then walk parents back from the target. For faster searches toward a known target, add a heuristic and you’ve turned Dijkstra into A*. To visualize the search, record the order cells are visited and animate it frame by frame.
Next project: a mini database index.