Shortest Path in Undirected Graph with Unit Distance
Problem link: https://www.geeksforgeeks.org/problems/shortest-path-in-undirected-graph-having-unit-distance/1
Problem Statement
You are given an undirected graph with V nodes and E edges. Each edge has a weight of 1. Given a source node src, find the shortest distance from src to all other nodes. If a node is unreachable, the distance should be -1.
Input
An adjacency list adj, number of nodes V, and a source node src.
Output
An array of integers representing the shortest distance to each node from src.
Example
Input: V = 5, E = 5, adj = [[1,3],[0,2],[1,4],[0,4],[3,2]], src = 0 Output: [0, 1, 2, 1, 2]
Brute Force
Intuition
Explore every possible path using DFS and keep track of the minimum distance for each node.
Approach
- Perform a recursive DFS starting from the source.
- For each path, maintain a current distance.
- Update the global distance array only if the new path is shorter than the previously recorded one.
Code (Java)
public void dfs(int node, int d, int[] dist, List<List<Integer>> adj) {
if (dist[node] != -1 && d >= dist[node]) return;
dist[node] = d;
for (int neighbor : adj.get(node)) {
dfs(neighbor, d + 1, dist, adj);
}
}
Complexity Analysis
In the worst case (a highly connected graph), DFS explores all possible permutations of paths, leading to factorial time complexity.
Optimal Solution
Intuition
Why BFS? In a graph where all edges have a weight of 1, BFS is the most efficient shortest-path algorithm. Unlike Dijkstra, which uses a Priority Queue to handle varying weights, BFS uses a simple Queue to explore nodes layer by layer. The first time a node is reached in BFS, it is guaranteed to be via the shortest path.
Approach
- Initialize a
distarray with -1 and setdist[src] = 0. - Add the source node to a FIFO Queue.
- While the queue is not empty:
- Pop the front node
u. - For every neighbor
vofu:- If
dist[v] == -1(not visited):- Set
dist[v] = dist[u] + 1. - Add
vto the queue.
- Set
- If
- Pop the front node
- Return the
distarray.
Code (Java)
class Solution {
public int[] shortestPath(int[][] edges, int n, int m, int src) {
List<List<Integer>> adj = new ArrayList<>();
for(int i=0; i<n; i++) adj.add(new ArrayList<>());
for(int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[src] = 0;
Queue<Integer> q = new LinkedList<>();
q.add(src);
while(!q.isEmpty()) {
int u = q.poll();
for(int v : adj.get(u)) {
if(dist[v] == -1) {
dist[v] = dist[u] + 1;
q.add(v);
}
}
}
return dist;
}
}
Complexity Analysis
Time: Each node and edge is processed exactly once. Space: O(V + E) for the adjacency list and O(V) for the distance array and queue.
Quick Revision (Brute Force)
- DFS explores all paths
- Inefficient: O(V!)
Quick Revision (Optimal)
- BFS is optimal for Unit Weights (Weight = 1)
- No need for Dijkstra's Priority Queue (avoids log V overhead)
- Time: O(V + E)
- Space: O(V + E)