Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

basic.sh

#!/usr/bin/env bash
set -euo pipefail
declare -A adj
adj[1]="2 3"
adj[2]="1 4"
adj[3]="1 4"
adj[4]="2 3 5"
adj[5]="4 6"
adj[6]="5"
src=1
dst=6
declare -A dist
declare -A parent
dist[$src]=0
parent[$src]=0
queue=("$src")
head=0
while [ "$head" -lt "${#queue[@]}" ]; do
	v=${queue[head]}
	head=$((head + 1))
	read -ra nbrs <<< "${adj[$v]}"
	for nb in "${nbrs[@]}"; do
		if [ -z "${dist[$nb]+_}" ]; then
			dist[$nb]=$((dist[$v] + 1))
			parent[$nb]=$v
			queue+=("$nb")
		fi
	done
done
path=()
node=$dst
while [ "$node" -ne 0 ]; do
	path+=("$node")
	node=${parent[$node]}
done
printf '['
sep=''
for ((k = ${#path[@]} - 1; k >= 0; k--)); do
	printf '%s%d' "$sep" "${path[k]}"
	sep=', '
done
printf ']\n'
printf '%d\n' "${dist[$dst]}"

Complexity

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

Implementation notes

Bash: a dist associative array doubles as the visited check, parent records predecessors (0 marks the source), and a head index walks the queue array.
The replay shows dist, parent, and the queue filling in, then the reconstructed path, matching the lesson spec.

layers equal distance BFS order equals distance in an unweighted graph.