Shortest Path, Nodes on Any Shortest Path, and Whether Alice Can Evade Bob

You are given an undirected, unweighted graph with `n` nodes, numbered `0` to `n - 1`, and a list of edges. Alice stands at node `a` and needs to reach a target node `t`. The interview had a base question and two follow-ups on the same graph. ### Constraints and Clarifications - Every edge has length 1, and the graph may be disconnected. - Assume the graph can be large, so each part should run in time close to linear in the number of nodes and edges. - Time is measured in steps: in one step a person moves along one edge. ### Clarifying Questions - What should be returned when `t` cannot be reached from `a`? - For the base question, is the length of a shortest path enough, or must an actual path be returned? - Can the edge list contain self-loops or duplicate edges? ### Part 1 — Shortest path for Alice Find a shortest path from `a` to `t`. ```hint Unweighted means layered Think about the order in which nodes are discovered when every edge costs the same. ``` #### What This Part Should Cover - The search, why it yields shortest distances when every edge has length 1, and how the path itself is recovered - An unreachable target and the case `a = t` - Time and space complexity ### Part 2 — Every node that can lie on a shortest path Find all nodes that appear on at least one shortest path from `a` to `t`. ```hint Look from the other end too Consider what a second search, started somewhere other than Alice's node, would tell you about each node. ``` #### What This Part Should Cover - An exact test for whether a node lies on some shortest path, and why it is correct - Why enumerating the shortest paths is not feasible - Complexity, and how the same idea applies to edges ### Part 3 — Bob tries to catch Alice Bob stands at another node `b`. Alice picks one of the shortest paths from `a` to `t` and starts walking it, and Bob starts moving at the same moment. Determine whether Alice can reach `t` safely, without being caught by Bob. ```hint Earliest arrival Once the movement rules are fixed, ask for each node on Alice's route how early Bob could be standing there. ``` #### Clarifying Questions for this Part - May Bob stand still during a step, or must he move along an edge in every step? - Is Alice caught only when both are on the same node at the same time, or also when they cross the same edge in opposite directions during one step? - If Bob reaches `t` at the same moment as Alice, or before her, is she caught? - Does Bob know which path Alice chose, so that the question is whether some shortest path is safe against every move Bob could make? #### What This Part Should Cover - A precise statement of the catch rules and of what "safe" means - A per-node (and, if needed, per-edge) safety condition, and how to evaluate it over all of Alice's candidate paths at once - How the answer changes if Bob may wait versus if he must keep moving - Complexity ### What a Strong Answer Covers - Breadth-first search used correctly, reasoning with distances rather than enumerating paths - A proof-level argument for the shortest-path membership test - Movement and capture rules agreed explicitly before any code is written for Part 3 - Recognition of how much the chosen rules simplify or complicate Part 3, with a correct algorithm for the rules chosen - Linear-time solutions and careful handling of unreachable nodes ### Follow-up Questions - How do Parts 2 and 3 change when edges have positive weights? - How would you handle several chasers starting at different nodes? - If Alice may take any path rather than a shortest one, how do you decide whether she can reach `t` safely?