Shortest Path Between Two Vertices in an Undirected Graph

BFS finds the shortest path between two vertices in an unweighted undirected graph by exploring vertices level by level, so the first time it reaches the destination it has taken the minimum number of edges.

No Dijkstra required here. Dijkstra solves the weighted case, where edges carry different costs. When every edge costs the same (as in an unweighted graph), BFS is both correct and faster to implement, with no priority queue overhead.

Why BFS Guarantees the Shortest Path

BFS processes vertices in waves. Wave 0 is the source itself. Wave 1 contains every vertex exactly one edge away. Wave 2 contains every vertex exactly two edges away, and so on. Because BFS marks each vertex visited before enqueuing it, no vertex is processed twice. Each vertex is therefore discovered at its true minimum distance from the source.

Compare this with DFS: a depth-first traversal might reach the destination via a long detour before finding the short route. DFS handles reachability correctly, but it gives no shortest-path guarantee on unweighted graphs.

The correctness of BFS follows by induction: if every vertex at distance k is correct when BFS begins processing wave k, then each unvisited neighbour of those vertices is assigned distance k+1 correctly. The base case (the source at distance 0) is trivially true. For the full proof with worked diagrams, see the BFS algorithm reference on GeeksForGeeks.

Graph Representation: Adjacency List

An adjacency list stores each vertex alongside the list of its neighbours. For a graph with V vertices and E edges, the adjacency list uses O(V + E) space, far more compact than a V-by-V adjacency matrix when the graph is sparse.

An undirected graph’s adjacency list is itself symmetric: every edge (u, v) appears in both adj[u] and adj[v]. This mirrored structure resembles the symmetric-pair pattern described in finding all symmetric pairs in an array. When you add an edge, you always update both directions.

In Python, a dictionary of lists works directly:

graph = {
    0: [1, 2, 4],
    1: [0, 2],
    2: [0, 1, 5],
    3: [4],
    4: [0, 3, 5],
    5: [2, 4]
}

This is the graph used in the worked example below. Every edge is stored twice: edge (0, 1) adds 1 to graph[0] and adds 0 to graph[1].

BFS with Parent Tracking

The standard BFS loop visits each vertex once. To reconstruct the path after BFS finishes, extend the loop with a parent map: whenever a new vertex is enqueued, record which vertex it was reached from.

from collections import deque

def bfs_shortest_path(graph, source, destination):
    if source == destination:
        return [source]

    visited = {source}
    parent = {source: None}
    queue = deque([source])

    while queue:
        current = queue.popleft()
        for neighbour in graph[current]:
            if neighbour not in visited:
                visited.add(neighbour)
                parent[neighbour] = current
                if neighbour == destination:
                    return _reconstruct(parent, source, destination)
                queue.append(neighbour)

    return []  # destination unreachable


def _reconstruct(parent, source, destination):
    path = []
    node = destination
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

One design choice worth noting: the destination check fires when a neighbour is enqueued, not when it is dequeued. Either placement is correct, but checking on enqueue exits one BFS level earlier and avoids adding unnecessary vertices to the queue.

The _reconstruct function walks the parent map from destination back to source, collecting each node. The loop ends when parent[node] is None, which only happens at the source (recorded as {source: None} at initialisation). Reversing the collected list gives the forward path.

Worked Example: 6-Vertex Graph

Consider a graph with vertices 0 through 5 and edges (0,1), (0,2), (0,4), (1,2), (2,5), (3,4), (4,5).

Find the shortest path from vertex 1 to vertex 5.

• Step 1: Start BFS. Enqueue vertex 1. visited = {1}, parent = {1: None}, queue = [1]
• Step 2: Dequeue 1. Neighbours of 1 are 0 and 2.
  • Enqueue 0, set parent[0] = 1.
  • Enqueue 2, set parent[2] = 1.
  • visited = {1, 0, 2}, queue = [0, 2]
• Step 3: Dequeue 0. Neighbours of 0 are 1 (visited), 2 (visited), and 4.
  • Enqueue 4, set parent[4] = 0.
  • visited = {1, 0, 2, 4}, queue = [2, 4]
• Step 4: Dequeue 2. Neighbours of 2 are 0 (visited), 1 (visited), and 5.
  • Neighbour 5 is the destination. Set parent[5] = 2. Return immediately.
• Step 5: Reconstruct path. Follow parent pointers: 5 → 2 → 1 → None. Reverse: 1 → 2 → 5. Edges used: 2.

Two longer paths also exist in this graph: 1 → 0 → 2 → 5 uses 3 edges and 1 → 0 → 4 → 5 uses 3 edges, but BFS reaches vertex 5 through vertex 2 first, at wave 2.

Multiple shortest paths of equal length can exist. BFS returns whichever one its adjacency-list ordering encounters first. All are valid.

Edge Cases

Source Equals Destination

Return [source] immediately before entering the BFS loop. Skipping this check would cause the BFS to mark the source as visited, potentially find the source as its own neighbour via a self-loop, and produce an empty or incorrect parent trace.

Disconnected Components

If BFS exhausts the queue without ever reaching the destination, the two vertices are in separate connected components. The function returns an empty list. Callers should check len(result) == 0 to distinguish “no path” from a valid single-node path.

Multiple Shortest Paths

As the worked example shows, more than one path of minimum length can exist. BFS returns one of them. Which one depends on the order in which neighbours appear in the adjacency list. In placement coding rounds, any correct minimum-length path satisfies the judge.

Self-Loop Edges

If the adjacency list contains a self-loop such as graph[2] = [0, 1, 5, 2], the visited set prevents an infinite loop. When BFS encounters vertex 2 as a neighbour of itself, vertex 2 is already in visited and is skipped.

Time and Space Complexity

Resource	Complexity	Reason
Time	O(V + E)	Each vertex enqueued once; each edge examined once
Queue space	O(V)	At most V entries in the queue at any point
Visited set	O(V)	One entry per vertex
Parent map	O(V)	One entry per vertex

The adjacency-list representation keeps the time term at O(V + E) rather than the O(V squared) cost that iterating over an adjacency matrix would impose. The space complexity of algorithms with examples article covers how to reason about queue and auxiliary-map costs in traversal algorithms.

For placement oral discussions, the answer is O(V + E) time and O(V) space. The cp-algorithms BFS article covers the 0-1 BFS variant for the related case where edge weights are 0 or 1 rather than all-equal.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

vector<int> bfsShortestPath(
    unordered_map<int, vector<int>>& graph, int src, int dst) {

    if (src == dst) return {src};

    unordered_set<int> visited = {src};
    unordered_map<int, int> parent;
    parent[src] = -1;
    queue<int> q;
    q.push(src);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int nb : graph[cur]) {
            if (visited.count(nb)) continue;
            visited.insert(nb);
            parent[nb] = cur;
            if (nb == dst) {
                vector<int> path;
                int node = dst;
                while (node != -1) {
                    path.push_back(node);
                    node = parent[node];
                }
                reverse(path.begin(), path.end());
                return path;
            }
            q.push(nb);
        }
    }
    return {};
}

Both the Python and C++ versions follow the same logic: build the parent map during BFS, then walk it backwards from destination to source. The C++ version uses -1 as the sentinel for the source’s parent entry because integers cannot be None.

BFS and shortest-path problems appear in coding rounds for CSE and IT candidates across placement season. Graph traversal is a near-constant in technical assessments, from service-company on-campus drives to product OAs. The parent-map reconstruction pattern (trace the path backwards, then reverse) is the exact technique to recognise and reproduce under timed conditions.

Once graph fundamentals are solid, the next layer is applying BFS intuition inside AI pipelines: retrieval-augmented generation (RAG) systems, knowledge-graph lookups, and agent routing all depend on graph traversal at their core. TinkerLLM has guided RAG-build projects that show exactly that connection, starting at ₹499.