Shortest Path in Undirected Graph with Unit Distance

Problem and examples

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.

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.

How it works

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.

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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int queue[MAX], front = 0, rear = 0;

void enqueue(int val) {
    queue[rear++] = val;
}

int dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front == rear;
}

int main() {
    int n = 4;
    int edges[][2] = {{0,1},{0,2},{1,3}};
    int m = sizeof(edges)/sizeof(edges[0]);

    int graph[MAX][MAX] = {0};
    int degree[MAX] = {0};
    int distance[MAX];

    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][degree[u]++] = v;
        graph[v][degree[v]++] = u;
    }

    for (int i = 0; i < n; i++) distance[i] = -1;
    distance[0] = 0;
    enqueue(0);

    while (!isEmpty()) {
        int current = dequeue();
        for (int i = 0; i < degree[current]; i++) {
            int neighbor = graph[current][i];
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[current] + 1;
                enqueue(neighbor);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", distance[i]);
    }
    printf("\n");
    return 0;
}

C++ implementation

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

int main() {
    int n = 4;
    vector<pair<int, int>> edges = {{0,1},{0,2},{1,3}};
    vector<vector<int>> graph(n);

    for (auto [u, v] : edges) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> distance(n, -1);
    queue<int> q;
    distance[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int current = q.front(); q.pop();
        for (int neighbor : graph[current]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[current] + 1;
                q.push(neighbor);
            }
        }
    }

    for (int d : distance) {
        cout << d << " ";
    }
    cout << endl;
    return 0;
}

Python implementation

from collections import deque

def shortest_path_unit_weight(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    distance = [-1] * n
    queue = deque([0])
    distance[0] = 0

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)

    return distance

print(shortest_path_unit_weight(4, [[0,1],[0,2],[1,3]]))

Java implementation

import java.util.*;

public class ShortestPathUnitWeight {
    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0,1},{0,2},{1,3}};

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int[] distance = new int[n];
        Arrays.fill(distance, -1);
        Queue<Integer> queue = new LinkedList<>();
        distance[0] = 0;
        queue.offer(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : graph.get(current)) {
                if (distance[neighbor] == -1) {
                    distance[neighbor] = distance[current] + 1;
                    queue.offer(neighbor);
                }
            }
        }

        System.out.println(Arrays.toString(distance));
    }
}

JavaScript implementation

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

  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;
}

console.log(shortestPathUnitWeight(4, [[0,1],[0,2],[1,3]]));

Go implementation

package main

import (
    "fmt"
)

func shortestPathUnitWeight(n int, edges [][]int) []int {
    graph := make([][]int, n)
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    distance := make([]int, n)
    for i := range distance {
        distance[i] = -1
    }
    queue := []int{0}
    distance[0] = 0

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[current] {
            if distance[neighbor] == -1 {
                distance[neighbor] = distance[current] + 1
                queue = append(queue, neighbor)
            }
        }
    }
    return distance
}

func main() {
    result := shortestPathUnitWeight(4, [][]int{{0,1},{0,2},{1,3}})
    fmt.Println(result)
}

Rust implementation

use std::collections::VecDeque;

fn shortest_path_unit_weight(n: usize, edges: &[(usize, usize)]) -> Vec<i32> {
    let mut graph = vec![vec![]; n];
    for &(u, v) in edges.iter() {
        graph[u].push(v);
        graph[v].push(u);
    }

    let mut distance = vec![-1; n];
    let mut queue = VecDeque::new();
    distance[0] = 0;
    queue.push_back(0);

    while let Some(current) = queue.pop_front() {
        for &neighbor in &graph[current] {
            if distance[neighbor] == -1 {
                distance[neighbor] = distance[current] + 1;
                queue.push_back(neighbor);
            }
        }
    }
    distance
}

fn main() {
    let result = shortest_path_unit_weight(4, &[(0,1),(0,2),(1,3)]);
    println!("{:?}", result);
}

Kotlin implementation

fun shortestPathUnitWeight(n: Int, edges: Array<IntArray>): IntArray {
    val graph = Array(n) { mutableListOf<Int>() }
    for ((u, v) in edges) {
        graph[u].add(v)
        graph[v].add(u)
    }

    val distance = IntArray(n) { -1 }
    val queue = ArrayDeque<Int>()
    distance[0] = 0
    queue.add(0)

    while (queue.isNotEmpty()) {
        val current = queue.removeFirst()
        for (neighbor in graph[current]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[current] + 1
                queue.add(neighbor)
            }
        }
    }
    return distance
}

fun main() {
    val result = shortestPathUnitWeight(4, arrayOf(intArrayOf(0,1), intArrayOf(0,2), intArrayOf(1,3)))
    println(result.joinToString())
}

Swift implementation

import Foundation

func shortestPathUnitWeight(_ n: Int, _ edges: [[Int]]) -> [Int] {
    var graph = Array(repeating: [Int](), count: n)
    for edge in edges {
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
    }

    var distance = Array(repeating: -1, count: n)
    var queue = [0]
    distance[0] = 0

    while !queue.isEmpty {
        let current = queue.removeFirst()
        for neighbor in graph[current] {
            if distance[neighbor] == -1 {
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)
            }
        }
    }
    return distance
}

let result = shortestPathUnitWeight(4, [[0,1],[0,2],[1,3]])
print(result)

TypeScript implementation

function shortestPathUnitWeight(n: number, edges: number[][]): number[] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }

  const distance: number[] = Array(n).fill(-1);
  const queue: number[] = [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;
}

console.log(shortestPathUnitWeight(4, [[0,1],[0,2],[1,3]]));