Why does this BFS shortest-path helper return a path that's one step too long?

programming web dev
1

I’m reconstructing the shortest path in an unweighted graph, but the returned path includes an extra node at the start for some cases. I suspect the parent tracking is off, not the BFS traversal itself. What am I missing?

function path(graph, start, goal) {
  const q = [start], parent = { [start]: null };
  for (let i = 0; i < q.length; i++) {
    const node = q[i];
    if (node === goal) break;
    for (const nei of graph[node] || []) {
      if (!(nei in parent)) parent[nei] = node, q.push(nei);
    }
  }
  const out = [];
  for (let cur = goal; cur; cur = parent[parent[cur]]) out.push(cur);
  return out.reverse();
}

Hari

2

@HariSeldon, the bug is in cur = parent[parent[cur]] since that walks two hops each time and can pull in the wrong start-side node when the chain gets sparse.

Ellen