Coursify

Shortest Paths in Unweighted Graphs: Why BFS Wins

Shortest Paths in Unweighted Graphs: Why BFS Wins

Verified Sources
Sep 25, 2026

In an unweighted graph, the algorithm guaranteed to find the shortest path (fewest edges) between two nodes is (iii) Breadth First Search (BFS).

The key idea is level-order exploration: BFS visits nodes in increasing distance (number of edges) from the source. Once the target is first discovered, the path used to discover it has the minimum number of edges.

dist and queue ensure BFS expands “outward” uniformly across the graph. By contrast:

  • Depth First Search (DFS) explores deeply and does not guarantee minimum-edge paths.
  • Kruskal’s and Prim’s algorithms compute a minimum spanning tree—they are not shortest-path algorithms between two specified vertices.

Footnotes

  1. Breadth-first search (BFS) — Wikipedia - Describes BFS level-order exploration and shortest-path property in unweighted graphs. ↩

BFS Shortest Path in Unweighted Graph (Conceptual)

Correct choice for the question

Given the options:

  1. Depth First Search (DFS) — not guaranteed shortest path
  2. Kruskal’s Algorithm — MST, not shortest path between two nodes
  3. Breadth First Search (BFS) — guaranteed shortest path in unweighted graphs
  4. Prim’s Algorithm — MST, not shortest path between two nodes

Therefore, the correct answer is (iii) Breadth First Search. 2

Footnotes

  1. Breadth-first search (BFS) — Wikipedia - Describes BFS level-order exploration and shortest-path property in unweighted graphs. ↩

  2. Breadth-first search (BFS) — Wikipedia - Includes typical complexity discussion (O(V+E)O(V+E)) for graph traversal with adjacency lists. ↩

How BFS guarantees shortest path in an unweighted graph

  1. 1
    Step 1

    Treat every edge as having the same cost (typically 1), so “shortest” means “minimum number of edges.”

    Footnotes

    1. Breadth-first search (BFS) — Wikipedia - Describes BFS level-order exploration and shortest-path property in unweighted graphs. ↩

  2. 2
    Step 2

    Put the source in a FIFO queue and set its distance to 0.

    Footnotes

    1. Breadth-first search (BFS) — Wikipedia - Includes typical complexity discussion (O(V+E)O(V+E)) for graph traversal with adjacency lists. ↩

  3. 3
    Step 3

    Each time you remove a node from the queue, explore its neighbors and assign each unvisited neighbor distance = current distance + 1.

    Footnotes

    1. Breadth-first search (BFS) — Wikipedia - Describes BFS level-order exploration and shortest-path property in unweighted graphs. ↩

  4. 4
    Step 4

    Because BFS explores in nondecreasing distance order, the first time you reach the target, that path has the minimum number of edges.

    Footnotes

    1. Breadth-first search (BFS) — Wikipedia - Describes BFS level-order exploration and shortest-path property in unweighted graphs. ↩

  5. 5
    Step 5

    Store a predecessor/parent pointer for each visited node and backtrack from target to source.

    Footnotes

    1. Breadth-first search (BFS) — Wikipedia - Includes typical complexity discussion (O(V+E)O(V+E)) for graph traversal with adjacency lists. ↩

Which algorithms solve shortest paths (between two nodes) in unweighted graphs?

BFS is guaranteed; DFS is not; Prim/Kruskal are MST algorithms.

Why the others don’t guarantee shortest paths

  • DFS: It can reach the target via a long route before exploring a shorter route (because it does not enforce increasing-distance “layers”).
  • Kruskal/Prim: They focus on building a minimum spanning tree (minimum total edge weight), not on minimizing the number of edges between two particular vertices. Even in weighted settings, MST does not generally equal shortest-path trees for every pair.

Footnotes

  1. Depth-first search (DFS) — Wikipedia - Explains DFS behavior (deep-first/backtracking), which does not ensure shortest paths. ↩

  2. Minimum spanning tree — Wikipedia - Defines MST as the goal of Prim’s and Kruskal’s algorithms and distinguishes it from shortest paths. ↩

Common exam-style clarifications

Pro Tip

If the question says “unweighted graph” and asks for “shortest path between two nodes,” your first reflex should be BFS (level-order traversal).

Common Mistake

Prim’s and Kruskal’s algorithms are for minimum spanning trees; they do not guarantee shortest paths between arbitrary node pairs.

Reasoning pipeline for multiple-choice shortest-path questions

Check whether edges are uniform

Step A

If unweighted (all edges equal), shortest path means minimum edges."

Use layer-by-layer traversal

Step B

BFS explores by increasing edge count, so first reach of target is optimal."

Eliminate MST-focused algorithms

Step C

Prim/Kruskal compute MST, not shortest path between two given nodes."

Avoid DFS for shortest-path guarantees

Step D

DFS depth-first order can produce a non-minimal edge path first."

Knowledge Check

Question 1 of 4
Q1Single choice

In an unweighted graph, which algorithm is guaranteed to find the shortest path between two nodes?

Explore Related Topics

1

Minimum Spanning Trees: Concept, Prim’s vs. Kruskal’s, and Complexity Analysis

2

Single-Source Shortest Path (SSSP): Applying Dijkstra to the Given Graph

3

Breadth-First Search as an Uninformed Search Strategy

Breadth‑First Search (BFS) expands the shallowest frontier nodes first using a FIFO queue and does not employ any heuristic function, making it an uninformed (blind) search strategy.

  • Classified as uninformed search because it relies only on the problem definition, not on h(n)h(n) or other estimates.
  • Complete for finite branching factors and optimal when all step costs are equal.
  • Tree‑search time and space are O(bd)O(b^{d}); graph‑search runs in O(∣V∣+∣E∣)O(|V|+|E|) time and O(∣V∣)O(|V|) space.
  • Main weakness is exponential memory growth, so it suits shallow goals with ample memory.
  • If step costs vary, uniform‑cost search should be used instead of BFS.
Browse all research articles