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❯

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.

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

Comments

Loading comments...