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.

ALGORITHMS · 05 / BREADTH-FIRST SEARCH

The Flood.

Q: What is breadth-first search (BFS)?

Breadth-first search is a graph traversal that explores a graph level by level: it visits all neighbours of the start, then all of their unvisited neighbours, and so on, spreading outward like a flood. It uses a FIFO queue and, on an unweighted graph, the first time it reaches a node it has found the shortest path there.

Q: What is the time complexity of BFS?

BFS runs in O(V + E) time, where V is the number of vertices and E the number of edges, because it visits every vertex once and examines every edge once. Space is O(V) for the queue and the visited set. On a grid of R rows and C columns, that is O(R × C).

Q: Why does BFS find the shortest path?

BFS expands nodes in order of their distance from the start: all nodes at distance 1, then distance 2, and so on. So the first time it reaches a node, no shorter route can exist — that distance is final. This guarantee holds only on unweighted graphs (every edge counts as one step); for weighted graphs you need Dijkstra's algorithm.

Q: What is the difference between BFS and DFS?

BFS (breadth-first) uses a FIFO queue and explores level by level, finding the shortest path in an unweighted graph. DFS (depth-first) uses a stack (or recursion) and dives as deep as possible before backtracking; it finds a path but not necessarily the shortest. BFS is better for shortest paths and nearest-node searches; DFS is better for exhaustive exploration, cycle detection, and topological sorting.

Q: Where is BFS used in real life?

Shortest paths in unweighted maps and grids, finding people within N connections in a social network, web crawling level by level, the 'fewest moves' solver for puzzles like a Rubik's cube or sliding puzzle, flood-fill in paint tools, and broadcast or peer-discovery in networks.

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.

QUICK CHECK

Did it stick?

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 / 5 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →

Roadmaps →

Prompt Engineering Roadmap

System Designs →

AI System Designs →

Labs →

Gradient Descent: The Descent