Mid · Graphs

Shortest Path in an Unweighted Graph

graph is an adjacency list indexed 0..n-1; each entry contains valid neighbor indices. Return the fewest directed edges from start to target, or -1 if unreachable. Start and target are valid indices. Edges have equal cost.

Examples

[[1,2],[3],[3],[]], 0, 3 → 2

Compare approaches

Repeated distance relaxation

Repeatedly improve distances along each edge. After V-1 passes every reachable shortest simple path is covered.

Time: O(V × (V + E)) · Space: O(V)

function distance(graph, start, target) { const d = Array(graph.length).fill(Infinity); d[start] = 0; for (let pass = 1; pass < graph.length; pass++) { for (let u = 0; u < graph.length; u++) for (const v of graph[u]) d[v] = Math.min(d[v], d[u] + 1); } return Number.isFinite(d[target]) ? d[target] : -1; }

Breadth-first search

Visit vertices by increasing distance. Mark them when enqueued and advance a head index instead of shifting the array.

Time: O(V + E) · Space: O(V)

function distance(graph, start, target) {
  const d = Array(graph.length).fill(-1), queue = [start];
  d[start] = 0;
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    if (u === target) return d[u];
    for (const v of graph[u]) if (d[v] === -1) {
      d[v] = d[u] + 1; queue.push(v);
    }
  }
  return -1;
}

Common traps

Plain BFS does not solve arbitrary weighted shortest paths.
Mark on enqueue to avoid duplicate queue entries.

Practise in the workspace →