Shortest Unweighted Path

01 · Question

Given an adjacency list with vertices 0..V-1 and valid start and target vertices, return a shortest path as a list of vertex IDs. The graph may be directed or undirected. Return [] if unreachable and [start] if the endpoints are equal.

Example: graph=[[1,2],[3],[3],[]], start=0, target=3 may return [0,1,3].

02 · Analysis

BFS discovers vertices in nondecreasing edge distance. Assign each vertex a predecessor at first discovery, which also marks it as queued. Stop when the target is removed from the queue, then follow predecessors backward and reverse the path. A DFS predecessor path is not necessarily shortest. Time O(V+E), auxiliary space O(V), plus O(path length) output. Edge weights must be equal for this distance argument.

03 · Solution

Reference solution

1from collections import deque
2
3def shortest_path(graph, start, target):
4    parent = {start: None}
5    queue = deque([start])
6    while queue:
7        node = queue.popleft()
8        if node == target:
9            break
10        for neighbor in graph[node]:
11            if neighbor not in parent:
12                parent[neighbor] = node
13                queue.append(neighbor)
14    if target not in parent:
15        return []
16    result = []
17    node = target
18    while node is not None:
19        result.append(node)
20        node = parent[node]
21    return result[::-1]

Number of Provinces