Shortest Path in an Undirected Graph with Unit Distance – Clear BFS Solution in Python

Find the Shortest Path in an Undirected Graph from a source to every other node when every edge costs 1. We build intuition for Breadth-First Search, walk through the code line by line, add a dry run, and finish with precise Big-O analysis.

Here’s the [Problem Link] to begin with.

1. Problem statement

You are given an undirected graph with n vertices (0 … n-1).
All edges have unit weight (cost = 1).

For a given source vertex src, return an array distance where

• distance[i] = the fewest edges needed to reach vertex i from src,
• If a vertex is unreachable, its distance is -1.

2. Example

n = 6
Edges:
0-1, 0-2, 1-3, 2-3, 3-4

distance = [0, 1, 1, 2, 3, -1]

3. Intuition & approach

3.1 Why Breadth-First Search (BFS)?

• Every edge costs the same (1).
• BFS explores the graph level by level:
  • Level 0 = source itself.
  • Level 1 = all vertices one edge away.
  • Level 2 = all vertices two edges away …
• The first time BFS reaches a vertex, it has already found the shortest possible path (fewest edges).

So BFS gives us the answer in a single scan.

3.2 Algorithm steps

1. Setup a queue to process vertices in order of their distance.
2. distance[src] = 0; push (src, 0) into the queue.
3. Pop a vertex (node, distSoFar)
   • For every neighbour adjNode
     • If the neighbour hasn’t been visited (distance == -1)
       • Set distance[adjNode] = distSoFar + 1
       • Push (adjNode, distSoFar + 1) into the queue.
4. Repeat until the queue is empty.
5. Return the distance array.

Because each vertex enters the queue once, the algorithm runs in linear time.

4. Python code

from collections import deque


class Solution:
    def shortestPath(self, adj, src):
        n = len(adj)                                  # number of vertices
        distance = [-1 for _ in range(n)]             # -1 = not reached yet
        queue = deque()

        queue.append([src, 0])                        # start from source
        distance[src] = 0

        while len(queue) != 0:
            node, dis_trav = queue.popleft()          # current vertex + distance
            for adjNode in adj[node]:                 # explore neighbours
                if distance[adjNode] == -1:           # first time we see it
                    distance[adjNode] = dis_trav + 1  # shortest path fixed
                    queue.append([adjNode, dis_trav + 1])

        return distance

5. Step-by-step code explanation

1. Lines 6-8 –
   • n stores the vertex count.
   • distance array starts at -1 for every vertex.
   • queue will maintain vertices to process in FIFO order.
2. Line 10 – Push the source (src, 0); distance to itself is 0.
3. Main while loop (Lines 12-17)
   • popleft() fetches the closest unprocessed vertex (node) and its current shortest distance (dis_trav).
   • Loop over every neighbour adjNode:
     • Unvisited? (distance = -1)
       • Set its distance to dis_trav + 1.
       • Enqueue it with this new distance.
   • Each neighbour enters the queue once, ensuring O(V + E) time.
4. Line 17 – When the queue empties, all reachable vertices have been assigned their minimum distances. The function returns the completed array.

6. Dry run on the earlier example graph

Queue state shown as [vertex, dist].

Matches [0, 1, 1, 2, 3, -1].

7. Complexity

V = n, E = number of edges.

8. Conclusion

• Breadth-First Search is the go-to tool for shortest paths when all edges cost the same.
• A single queue and a distance array are enough, no fancy data structures.
• Because we mark a vertex the first time we see it, its distance is already minimal.
• The solution is linear, easy to code, and scales to very large sparse graphs.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.