Understanding the Problem
We are given an undirected graph where all edges have a unit distance (i.e., weight = 1).
Our goal is to find the shortest path from the source node (usually node 0) to all other nodes in the graph.
This is a classic case for using Breadth-First Search (BFS), because BFS is guaranteed to find the shortest path in graphs with unweighted or unit-weighted edges.
To achieve this, we will construct the graph using an adjacency list and traverse it level by level using BFS, keeping track of the shortest distance to each node.
Step-by-Step Solution with Example
Step 1: Represent the graph
We use an adjacency list to store the graph. Each node maps to a list of its neighbors.
This representation is efficient and simple to use for BFS.
Step 2: Initialize the distance array
Create a distance[]
array with size equal to the number of nodes.
Initially, set all values to -1
to indicate that they are not reachable.
Set distance[0]
to 0
since the distance from the source to itself is always zero.
Step 3: Perform BFS
Use a queue to start from the source node (node 0). At each step:
- Dequeue the current node
- For each of its neighbors, if that neighbor's distance is still
-1
, set it to distance[current] + 1
and enqueue it
This ensures that each node is visited in the shortest possible way.
Step 4: Example Walkthrough
Let's consider the following simple graph:
Input:
n = 5
edges = [
[0, 1],
[0, 2],
[1, 3],
[2, 4]
]
Graph visualization:
- Node 0 is connected to 1 and 2
- Node 1 connects further to 3
- Node 2 connects to 4
Using BFS starting from node 0:
- Distance to 0: 0
- Distance to 1: 1 (via 0 → 1)
- Distance to 2: 1 (via 0 → 2)
- Distance to 3: 2 (via 0 → 1 → 3)
- Distance to 4: 2 (via 0 → 2 → 4)
Final distance array:
[0, 1, 1, 2, 2]
Edge Cases
- Disconnected nodes: If a node is unreachable from the source, its distance will remain
-1
- Single-node graph: The distance array will be
[0]
since it's the only node
- No edges: All nodes except the source will remain unreachable
- Cycles: BFS still guarantees shortest paths because it visits each node only once using the smallest possible number of edges
Finally
Using BFS for shortest paths in an undirected unit-weight graph is both efficient and intuitive.
The key idea is to explore all neighbors at each level before going deeper, which ensures minimum edge traversal.
This method easily adapts to real-world problems like social network connections, network packet routing, and more.
Comments
Loading comments...