What is the difference between BFS and Dijkstra's algorithm?

BFS finds the shortest path by number of edges on an unweighted graph using a simple FIFO queue. Dijkstra finds the shortest path by total edge weight on a weighted graph using a priority queue. BFS is exactly the special case of Dijkstra where every edge weight is 1.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 05 / BREADTH-FIRST SEARCH

The Flood.

Watch the explainer

Find your way through the maze by hand — then release a flood from the start that spreads out in rings. The moment it touches the exit, it has found the shortest path.

THE GIST · 20 SECONDS

Breadth-first search explores a graph level by level: every neighbour of the start first, then their neighbours, spreading out like water. It uses a FIFO queue, and because it reaches nodes in order of distance, the first time the flood touches a node is the shortest path there. On an unweighted maze, that's a guarantee — and it runs in O(V + E).

Frontierthe current ring being explored
QueueFIFO — first in, first out
Visitedseen already — never re-add
Layerall cells at the same distance

① Find your own way → ② Release the flood → ③ Race BFS vs DFS

start exit wall flooded (by distance) shortest path

The flood spreads one ring at a time, so cells are reached in distance order. That ordering is exactly why the first time BFS touches the exit, it's the shortest way there.

UNDER THE HOOD

What you just played, written down

You walked it, watched the flood spread in rings, and saw DFS dive past the shortest path. Here's the same thing as code.

How the Tide thinks — five steps

Seed the queue. Put the start in a FIFO queue; mark it visited at distance 0.
Dequeue the front. Take the oldest cell — the closest unprocessed one.
Visit neighbours. For each unvisited neighbour, mark it visited, set its distance to current + 1, record where it came from, and enqueue it.
Repeat until the queue is empty (or you dequeue the goal).
Rebuild the path. Walk the "came-from" links back from the goal to the start.

WHY IT FINDS THE SHORTEST PATH

A FIFO queue drains cells in the order they were added — which is distance order. So the first time a cell is reached, no shorter path can exist. This holds only when every step costs the same (unweighted); add weights and you need Dijkstra.

The algorithm

function bfs(graph, start, goal):
    queue = [start]                  # FIFO
    visited = {start}
    dist[start] = 0
    while queue not empty:
        u = queue.dequeue()          # oldest first
        if u == goal: break
        for v in neighbours(u):
            if v not in visited:
                visited.add(v)
                dist[v] = dist[u] + 1
                prev[v] = u
                queue.enqueue(v)
    return rebuild(prev, goal)

TIMEO(V + E)every node + edge once

SPACEO(V)queue + visited set

Solved by hand — the layers for the maze above

Each ring the flood reaches, how far it is, and how many new cells join it.

↔ BFS vs DFS

BFS (queue) explores level by level and finds the shortest path. DFS (stack) dives deep first — great for exhaustive search, cycles and topological sort, but it does not guarantee the shortest path.

↔ BFS vs Dijkstra

BFS is just Dijkstra with every edge weight = 1. The moment steps have different costs, swap the FIFO queue for a priority queue and you have Dijkstra.

★ Where it's used

Shortest paths on unweighted maps, "people within N connections", web crawling, fewest-moves puzzle solvers, and flood-fill in paint tools.

The picture: distance rings on the page’s maze

The 9 × 7 maze from the playable section, with each open cell labelled by how many steps it is from the start. The numbers rise in rings because a first-in first-out queue hands out cells in distance order, so the exit receives its label, 14, the first time it is reached. The highlighted route is one of several shortest paths.

Complexity and trade-offs

Case	Time	Space	Why
Breadth-first search	`O(V + E)`	`O(V)`	Each cell enters the queue once and each edge is looked at once. On an R × C grid that is `O(R·C)`.
Depth-first search	`O(V + E)`	`O(V)`	Same cost, but the first path it finds is not the shortest: 26 steps here against 14.
Dijkstra	`O((V + E) log V)`	`O(V)`	Needed when edges have different costs. BFS is the special case where all costs are 1.
0-1 BFS	`O(V + E)`	`O(V)`	For edges that cost 0 or 1: a double-ended queue instead of a heap.
Bidirectional BFS	about `O(b^d/2)` per side	`O(b^d/2)`	Searches from both ends and stops when the two meet; helps when the branching factor `b` is large.

On the page’s maze, 49 of the 63 cells are open. BFS took 48 of them off the queue before reaching the exit, and the queue never held more than 6 cells at once: the frontier is a ring, not the whole map. Space is therefore bounded by the widest layer in practice, but O(V) in the worst case, and the visited set is the part that always costs O(V). What you give up is cheapness on huge, branching graphs: BFS must hold an entire layer, and a layer can be most of the graph.

Common mistakes

Marking visited when you dequeue
Mark a cell the moment it is put on the queue, not when it comes off. On the page’s maze, marking at dequeue pushed 66 entries on the queue before the exit was reached, against 49 cells discovered with marking at enqueue. The distances stay right, but the duplicates cost memory and time, and on dense graphs it multiplies.
No visited set at all
Without one, a cell is re-queued from every neighbour, and in a grid every cell has a way back. On the page’s maze the layers of the queue grow 2, 4, 9, 20, 52 … and the 14th layer alone has 1,025,006 entries, while the real frontier at that depth is 2 cells. On an open grid with a cycle the loop never ends.
Expecting a shortest path from a stack
Swap the queue for a stack and the same code is depth-first search. On the same maze it expands 41 cells and returns a 26-step route; the shortest is 14. Both look like “graph search”, but only the first-in first-out order gives distances.
Using BFS when edges have costs
BFS minimises the number of edges, not their total cost. With A–B costing 1, B–C costing 1 and a direct A–C costing 10, BFS reports the one-edge route to C with cost 10, while the two-edge route costs 2. Use Dijkstra, or 0-1 BFS if costs are only 0 and 1.
Off-by-one between steps and cells
The route from start to exit on the page’s maze has 15 cells and 14 steps. Distance counts edges, so initialise the start at 0, not 1, and decide up front whether the problem asks for steps or cells.

Where this shows up

Shortest route on a map or grid
Any unweighted grid or graph: game maps, robot floor plans, puzzle boards where each move costs the same. It also answers “which cells are reachable within k steps” by stopping after k layers.
Fewest moves in a puzzle
Treat each configuration as a node and each legal move as an edge, and BFS finds the fewest-move solution to a sliding puzzle or word ladder. The cost is the number of distinct states, which is what to estimate before choosing it.
Layers of a network
“People within three connections” in a social graph, and crawling a site level by level, are BFS stopped at a given depth. The layer number is the answer.
Connected regions and flood fill
Starting from one cell and spreading to equal-coloured neighbours marks a connected region, as in a paint bucket tool or counting islands in a grid. BFS and DFS both work there; only the order differs.

RUN IT YOURSELF

BFS shortest path, in Python & TypeScript

The same breadth-first search in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS

A FIFO queue holds the frontier, seeded with the start (step 1).
Always take the oldest node — that processes nodes in distance order (step 2).
Record each unseen neighbour one ring further out; the first time you reach a node is the shortest way there (step 3).
If the queue drains without reaching the goal, it is unreachable → -1 (step 4).

CPython · WebAssembly

# Breadth-first search: explore a graph in rings from the start,
# so the first time we reach a node is the shortest path. O(V + E).
from collections import deque

def bfs_shortest(graph, start, goal):
    # STEP 1 - a FIFO queue, seeded with the start.
    queue = deque([start])
    # distance[start] = 0; this map doubles as the "visited" set.
    distance = {start: 0}

while queue:
        # STEP 2 - take the oldest node (closest unprocessed one).
        node = queue.popleft()
        if node == goal:
            return distance[node]

# STEP 3 - record each unseen neighbour one ring further out.
        for nbr in graph[node]:
            if nbr not in distance:
                distance[nbr] = distance[node] + 1
                queue.append(nbr)

# STEP 4 - queue drained without reaching the goal: unreachable.
    return -1

graph = {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
    "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],
}
print("A -> F in", bfs_shortest(graph, "A", "F"), "steps")

// Breadth-first search: explore a graph in rings from the start,
// so the first time we reach a node is the shortest path. O(V + E).
type Graph = Record<string, string[]>;

function bfsShortest(graph: Graph, start: string, goal: string): number {
  // STEP 1 - a FIFO queue, seeded with the start.
  const queue: string[] = [start];
  // distance[start] = 0; this map doubles as the "visited" set.
  const distance: Record<string, number> = { [start]: 0 };

while (queue.length > 0) {
    // STEP 2 - take the oldest node (closest unprocessed one).
    const node = queue.shift()!;
    if (node === goal) return distance[node];

// STEP 3 - record each unseen neighbour one ring further out.
    for (const nbr of graph[node]) {
      if (!(nbr in distance)) {
        distance[nbr] = distance[node] + 1;
        queue.push(nbr);
      }
    }
  }

// STEP 4 - queue drained without reaching the goal: unreachable.
  return -1;
}

const graph: Graph = {
  A: ["B", "C"], B: ["A", "D", "E"], C: ["A", "F"],
  D: ["B"], E: ["B", "F"], F: ["C", "E"],
};
console.log("A -> F in", bfsShortest(graph, "A", "F"), "steps");

▶ Watch it explained

Breadth-First Search: Time and Space Complexity, From First Principles

QUICK CHECK

Did it stick?

See every answer, with the reasoning

What data structure does BFS use to decide what to explore next?
Answer: A FIFO queue — BFS uses a FIFO queue, so cells come out in the order they went in — which is distance order.
Why does BFS find the shortest path on an unweighted graph?
Answer: It reaches cells in order of distance, so the first arrival is shortest — Expanding by distance means no shorter route can reach a cell after BFS first does — that distance is final.
How does DFS differ from BFS?
Answer: DFS dives deep first and does not guarantee the shortest path — DFS uses a stack and follows one branch to its end before backtracking, so it finds a path but not necessarily the shortest.

FAQ

Breadth-first search, answered

What is breadth-first search (BFS)?

BFS explores a graph level by level from the start, using a FIFO queue. Because it reaches cells in distance order, the first time it touches a cell is the shortest path there (on an unweighted graph).

What is the time complexity of BFS?

O(V + E) — every vertex and edge is examined once. Space is O(V) for the queue and visited set; on an R×C grid that's O(R×C).

Why does BFS find the shortest path?

It expands cells in order of distance — all at distance 1, then 2, and so on. So the first time a cell is reached, no shorter route can exist. This holds only on unweighted graphs; weighted graphs need Dijkstra.

What is the difference between BFS and DFS?

BFS (queue) goes level by level and finds the shortest path. DFS (stack/recursion) dives deep first — good for exhaustive search, cycle detection and topological sort, but it doesn't guarantee the shortest path.

BFS vs Dijkstra's algorithm?

BFS finds the fewest-edges path on an unweighted graph with a FIFO queue. Dijkstra finds the lowest-weight path with a priority queue. BFS is the special case of Dijkstra where all edge weights are 1.

Where is BFS used in real life?

Shortest paths on unweighted maps, "people within N connections", web crawling, fewest-moves puzzle solvers, and flood-fill in paint tools.

Finished this one? 0 / 99 Algorithms done

NextBuild Order: DFS & Topological Sort Next on the “Walking a graph” ladder · rung 2 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Challenges →