Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Shortest Path in Unweighted Graph

HARDProblemSolveExternal Links

Description

You are given an undirected graph with V vertices numbered from 0 to V - 1 and E edges. Each edge is represented as [u, v], meaning there is a bidirectional connection between vertex u and vertex v. All edges have unit weight (cost of 1).

Given a source vertex src, find the shortest distance from src to every other vertex in the graph. If a vertex is not reachable from the source, its distance should be reported as -1.

Examples

Example 1

Input: V = 9, E = 10, edges = [[0,1],[0,3],[1,2],[3,4],[4,5],[2,6],[5,6],[6,7],[6,8],[7,8]], src = 0

Output: [0, 1, 2, 1, 2, 3, 3, 4, 4]

Explanation:

  • Vertex 0 is the source, so dist[0] = 0.
  • Vertex 1 is directly connected to 0 → dist[1] = 1.
  • Vertex 3 is directly connected to 0 → dist[3] = 1.
  • Vertex 2 is reached via 0→1→2 → dist[2] = 2.
  • Vertex 4 is reached via 0→3→4 → dist[4] = 2.
  • Vertex 5 is reached via 0→3→4→5 → dist[5] = 3.
  • Vertex 6 is reached via 0→1→2→6 → dist[6] = 3.
  • Vertex 7 is reached via 0→1→2→6→7 → dist[7] = 4.
  • Vertex 8 is reached via 0→1→2→6→8 → dist[8] = 4.

Example 2

Input: V = 4, E = 2, edges = [[0,3],[1,3]], src = 3

Output: [1, 1, -1, 0]

Explanation:

  • Vertex 3 is the source, so dist[3] = 0.
  • Vertex 0 is directly connected to 3 → dist[0] = 1.
  • Vertex 1 is directly connected to 3 → dist[1] = 1.
  • Vertex 2 has no edges connecting it to any reachable vertex → dist[2] = -1 (unreachable).

Constraints

  • 1 ≤ V ≤ 10^4
  • 0 ≤ E ≤ V × (V - 1) / 2
  • 0 ≤ edges[i][0], edges[i][1] < V
  • 0 ≤ src < V

Editorial

Brute Force - Dijkstra's Algorithm

Intuition

Whenever we hear "shortest path," the first algorithm that comes to mind is often Dijkstra's. And it works perfectly here — Dijkstra's algorithm handles non-negative edge weights, and unit weight (1) is certainly non-negative.

The idea is to maintain a distance array and a min-heap (priority queue). We start with the source vertex at distance 0, and repeatedly extract the vertex with the smallest known distance, then relax all its neighbors. "Relaxing" means checking: can I reach this neighbor more cheaply by going through the vertex I just extracted?

With a priority queue, Dijkstra efficiently picks the next closest unvisited vertex. For this unit-weight graph, it still gives correct results — but the priority queue does extra work maintaining sorted order when, in reality, all edge weights are identical. This is like using a sports car to drive to the mailbox next door: it works, but there is a simpler tool for the job.

Step-by-Step Explanation

Let's trace Dijkstra on a small graph: V=6, edges = [[0,1],[0,2],[1,3],[2,4],[3,5],[4,5]], src = 0.

Adjacency list:

  • 0: [1, 2]
  • 1: [0, 3]
  • 2: [0, 4]
  • 3: [1, 5]
  • 4: [2, 5]
  • 5: [3, 4]

Step 1: Initialize dist = [0, inf, inf, inf, inf, inf]. Push (0, 0) into the min-heap.

Step 2: Extract (dist=0, vertex=0). Relax neighbors:

  • Vertex 1: dist[1] = min(inf, 0+1) = 1. Push (1, 1).
  • Vertex 2: dist[2] = min(inf, 0+1) = 1. Push (1, 2).
  • dist = [0, 1, 1, inf, inf, inf]

Step 3: Extract (dist=1, vertex=1). Relax neighbors:

  • Vertex 0: dist[0] = 0 ≤ 1+1. No update.
  • Vertex 3: dist[3] = min(inf, 1+1) = 2. Push (2, 3).
  • dist = [0, 1, 1, 2, inf, inf]

Step 4: Extract (dist=1, vertex=2). Relax neighbors:

  • Vertex 0: dist[0] = 0 ≤ 1+1. No update.
  • Vertex 4: dist[4] = min(inf, 1+1) = 2. Push (2, 4).
  • dist = [0, 1, 1, 2, 2, inf]

Step 5: Extract (dist=2, vertex=3). Relax neighbors:

  • Vertex 1: dist[1] = 1 ≤ 2+1. No update.
  • Vertex 5: dist[5] = min(inf, 2+1) = 3. Push (3, 5).
  • dist = [0, 1, 1, 2, 2, 3]

Step 6: Extract (dist=2, vertex=4). Relax neighbors:

  • Vertex 2: dist[2] = 1 ≤ 2+1. No update.
  • Vertex 5: dist[5] = 3 ≤ 2+1. No update.
  • dist = [0, 1, 1, 2, 2, 3]

Step 7: Extract (dist=3, vertex=5). No further updates.

Result: dist = [0, 1, 1, 2, 2, 3]. No unreachable vertices.

Dijkstra on Unit-Weight Graph — Watch Dijkstra's algorithm use a priority queue to process vertices in distance order, discovering shortest paths in a unit-weight graph.

Algorithm

  1. Build an adjacency list from the edge list.
  2. Initialize a distance array with infinity for all vertices. Set dist[src] = 0.
  3. Create a min-heap (priority queue) and push (0, src).
  4. While the heap is not empty:
    a. Extract the vertex u with the smallest distance.
    b. For each neighbor v of u: if dist[u] + 1 < dist[v], update dist[v] = dist[u] + 1 and push (dist[v], v).
  5. Replace any remaining infinity values with -1 (unreachable vertices).
  6. Return the distance array.

Code

#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> shortestPath(int V, vector<vector<int>>& edges, int src) {
        // Build adjacency list
        vector<vector<int>> adj(V);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        vector<int> dist(V, INT_MAX);
        dist[src] = 0;
        
        // Min-heap: (distance, vertex)
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.push({0, src});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue; // Skip stale entries
            
            for (int v : adj[u]) {
                if (dist[u] + 1 < dist[v]) {
                    dist[v] = dist[u] + 1;
                    pq.push({dist[v], v});
                }
            }
        }
        
        // Mark unreachable vertices as -1
        for (int i = 0; i < V; i++) {
            if (dist[i] == INT_MAX) dist[i] = -1;
        }
        return dist;
    }
};
import heapq

class Solution:
    def shortestPath(self, V: int, edges: list[list[int]], src: int) -> list[int]:
        # Build adjacency list
        adj = [[] for _ in range(V)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        dist = [float('inf')] * V
        dist[src] = 0
        
        # Min-heap: (distance, vertex)
        heap = [(0, src)]
        
        while heap:
            d, u = heapq.heappop(heap)
            
            if d > dist[u]:  # Skip stale entries
                continue
            
            for v in adj[u]:
                if dist[u] + 1 < dist[v]:
                    dist[v] = dist[u] + 1
                    heapq.heappush(heap, (dist[v], v))
        
        # Mark unreachable vertices as -1
        return [d if d != float('inf') else -1 for d in dist]
import java.util.*;

class Solution {
    public int[] shortestPath(int V, int[][] edges, int src) {
        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        
        // Min-heap: (distance, vertex)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, src});
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], u = curr[1];
            
            if (d > dist[u]) continue; // Skip stale entries
            
            for (int v : adj.get(u)) {
                if (dist[u] + 1 < dist[v]) {
                    dist[v] = dist[u] + 1;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
        
        // Mark unreachable vertices as -1
        for (int i = 0; i < V; i++) {
            if (dist[i] == Integer.MAX_VALUE) dist[i] = -1;
        }
        return dist;
    }
}

Complexity Analysis

Time Complexity: O((V + E) log V)

Each vertex is extracted from the priority queue at most once (stale entries are skipped). Each edge causes at most one push into the heap. Each heap operation (push or pop) takes O(log V). So the total work is O(V log V) for extractions plus O(E log V) for edge relaxations, giving O((V + E) log V).

Space Complexity: O(V + E)

The adjacency list takes O(V + E) space. The distance array takes O(V). The priority queue can hold at most O(V) entries at any time (at most one entry per vertex in the optimal case, though stale entries may increase this temporarily).

Why This Approach Is Not Efficient

Dijkstra's algorithm is designed for graphs with varying edge weights, where the priority queue is essential to decide which vertex to process next. But in our problem, every edge has the same weight (1). This means the priority queue is doing unnecessary work — maintaining a sorted order among distances that naturally increase by exactly 1 at each level.

The O(log V) cost per heap operation is pure overhead. When all weights are equal, the vertices discovered at distance d are always processed before those at distance d+1. This is precisely what a simple FIFO queue (like in BFS) provides for free — O(1) per enqueue/dequeue instead of O(log V).

The key insight is: in an unweighted graph, BFS inherently discovers vertices in shortest-distance order. The first time BFS reaches a vertex, that path is guaranteed to be the shortest. No priority queue needed, no sorting overhead — just a plain queue.

Optimal Approach - BFS (Breadth-First Search)

Intuition

BFS is tailor-made for finding shortest paths in unweighted graphs. The algorithm explores vertices layer by layer: first all vertices at distance 0 (just the source), then all at distance 1 (direct neighbors of source), then all at distance 2, and so on.

Why does this guarantee shortest paths? Because BFS uses a FIFO queue. When we dequeue a vertex at distance d, all its unvisited neighbors are at distance d+1. Since we process all distance-d vertices before any distance-(d+1) vertices, the first time we discover any vertex is necessarily through the shortest path.

Think of dropping a stone into still water. The ripples spread outward one level at a time — the first ripple to reach any point is the shortest path from the center. BFS works exactly the same way: it spreads outward from the source, and the first visit to each vertex is optimal.

For unreachable vertices, they simply never get dequeued, so their distance remains at the initial value, which we convert to -1.

Diagram showing BFS expanding layer by layer from a source vertex, with concentric circles representing distance levels 0, 1, 2, and 3
Diagram showing BFS expanding layer by layer from a source vertex, with concentric circles representing distance levels 0, 1, 2, and 3

Step-by-Step Explanation

Let's trace BFS on the same graph: V=6, edges = [[0,1],[0,2],[1,3],[2,4],[3,5],[4,5]], src = 0.

Adjacency list:

  • 0: [1, 2]
  • 1: [0, 3]
  • 2: [0, 4]
  • 3: [1, 5]
  • 4: [2, 5]
  • 5: [3, 4]

Step 1: Initialize dist = [0, -1, -1, -1, -1, -1]. Enqueue source vertex 0. Mark dist[0] = 0.

Step 2: Dequeue vertex 0 (dist=0). Check neighbors:

  • Vertex 1: unvisited (dist=-1). Set dist[1] = 0+1 = 1. Enqueue 1.
  • Vertex 2: unvisited (dist=-1). Set dist[2] = 0+1 = 1. Enqueue 2.
  • Queue: [1, 2]

Step 3: Dequeue vertex 1 (dist=1). Check neighbors:

  • Vertex 0: already visited (dist=0). Skip.
  • Vertex 3: unvisited. Set dist[3] = 1+1 = 2. Enqueue 3.
  • Queue: [2, 3]

Step 4: Dequeue vertex 2 (dist=1). Check neighbors:

  • Vertex 0: already visited. Skip.
  • Vertex 4: unvisited. Set dist[4] = 1+1 = 2. Enqueue 4.
  • Queue: [3, 4]

Step 5: Dequeue vertex 3 (dist=2). Check neighbors:

  • Vertex 1: already visited. Skip.
  • Vertex 5: unvisited. Set dist[5] = 2+1 = 3. Enqueue 5.
  • Queue: [4, 5]

Step 6: Dequeue vertex 4 (dist=2). Check neighbors:

  • Vertex 2: already visited. Skip.
  • Vertex 5: already visited (dist=3). Skip.
  • Queue: [5]

Step 7: Dequeue vertex 5 (dist=3). No unvisited neighbors. Queue is empty.

Result: dist = [0, 1, 1, 2, 2, 3].

BFS — Layer-by-Layer Shortest Path Discovery — Watch BFS explore the graph layer by layer using a simple FIFO queue. Each vertex is discovered at its shortest distance from the source — no priority queue needed.

Algorithm

  1. Build an adjacency list from the edge list.
  2. Initialize a distance array with -1 for all vertices. Set dist[src] = 0.
  3. Create a FIFO queue and enqueue the source vertex.
  4. While the queue is not empty:
    a. Dequeue vertex u.
    b. For each neighbor v of u: if dist[v] == -1 (unvisited), set dist[v] = dist[u] + 1 and enqueue v.
  5. Return the distance array (vertices still at -1 are unreachable).

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> shortestPath(int V, vector<vector<int>>& edges, int src) {
        // Build adjacency list
        vector<vector<int>> adj(V);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        // Initialize distances to -1 (unvisited)
        vector<int> dist(V, -1);
        dist[src] = 0;
        
        // BFS with simple FIFO queue
        queue<int> q;
        q.push(src);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (int v : adj[u]) {
                if (dist[v] == -1) { // Unvisited
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        
        return dist;
    }
};
from collections import deque

class Solution:
    def shortestPath(self, V: int, edges: list[list[int]], src: int) -> list[int]:
        # Build adjacency list
        adj = [[] for _ in range(V)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        # Initialize distances to -1 (unvisited)
        dist = [-1] * V
        dist[src] = 0
        
        # BFS with simple FIFO queue
        queue = deque([src])
        
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if dist[v] == -1:  # Unvisited
                    dist[v] = dist[u] + 1
                    queue.append(v)
        
        return dist
import java.util.*;

class Solution {
    public int[] shortestPath(int V, int[][] edges, int src) {
        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        // Initialize distances to -1 (unvisited)
        int[] dist = new int[V];
        Arrays.fill(dist, -1);
        dist[src] = 0;
        
        // BFS with simple FIFO queue
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(src);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) { // Unvisited
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }
        
        return dist;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

BFS visits each vertex exactly once (the dist[v] == -1 check prevents revisits) and examines each edge exactly twice (once from each endpoint in an undirected graph). Every queue operation — enqueue and dequeue — takes O(1). So the total work is O(V) for vertex processing plus O(E) for edge examination, giving O(V + E). This is strictly better than Dijkstra's O((V + E) log V) because we eliminated the logarithmic heap overhead entirely.

Space Complexity: O(V + E)

The adjacency list takes O(V + E). The distance array takes O(V). The queue holds at most O(V) elements at any point (in the worst case, all vertices could be enqueued). Total: O(V + E).