Shortest Path in Undirected Graph with Unit Distance

Problem Statement❯

Given an Undirected Graph with unit weights (i.e., every edge has weight 1), the task is to compute the shortest path from a given source node (assumed to be 0) to all other nodes in the graph.

If a node is unreachable from the source, return -1 for that node.

Examples❯

Graph	Shortest Distances	Description
{ 0: [1, 2], 1: [0, 3], 2: [0], 3: [1] }	[0, 1, 1, 2]	Node 0 connects directly to 1 and 2; node 3 is two steps away.
{ 0: [1], 1: [0], 2: [] }	[0, 1, -1]	Node 2 is disconnected from the rest of the graph.
{}	[]	Empty graph with no nodes.
{ 0: [] }	[0]	Single node with no edges; self-distance is 0.

Solution❯

To solve this problem, we use Breadth-First Search (BFS). BFS guarantees the shortest path in unweighted graphs (or graphs with unit weight edges) since it explores nodes level by level from the source.

We maintain a distance[] array initialized to -1 for all nodes and set distance[0] to 0 (since the distance from the source to itself is zero).

As we perform BFS from the source, for every neighbor not visited yet, we set its distance to distance[current] + 1 and enqueue it. This way, each node gets the minimum distance from the source.

If a node remains with a distance of -1, it means it is unreachable from the source node.

Algorithm Steps❯

Initialize an array distance with -1 for all nodes.
Set distance[0] = 0 as the source is node 0.
Initialize a queue and enqueue node 0.
While the queue is not empty:

Dequeue the front node as current.
For each neighbor of current:

If distance[neighbor] == -1, set distance[neighbor] = distance[current] + 1 and enqueue the neighbor.

Return the distance array.

Code

JavaScript

function shortestPathUnitWeight(n, edges) {
  const graph = Array.from({ length: n }, () => []);

  // Build the undirected graph
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const distance = new Array(n).fill(-1);
  const queue = [0];
  distance[0] = 0;

  while (queue.length > 0) {
    const current = queue.shift();
    for (const neighbor of graph[current]) {
      if (distance[neighbor] === -1) {
        distance[neighbor] = distance[current] + 1;
        queue.push(neighbor);
      }
    }
  }

  return distance;
}

// Example usage:
console.log("Shortest distances:", shortestPathUnitWeight(4, [[0,1],[0,2],[1,3]])); // Output: [0,1,1,2]
console.log("Disconnected graph:", shortestPathUnitWeight(3, [[0,1]])); // Output: [0,1,-1]

⬅ Previous TopicAlien Dictionary Character Order

Next Topic ⮕Shortest Path in DAG using Topological Sort