Implementation lab in Shortest Paths and Relaxation

Mission

Use BFS to find the minimum number of edges.

Learning outcome: Implement unweighted shortest hops

Correctness contract

Invariant: Each stored distance is a discovered path cost, and relaxation only improves it with a valid path.

Required technique: Use BFS distances initialized to an unreachable sentinel.

Complexity target: time O(V+E); space O(V+E).

Input and output

Input: V and E, then E undirected vertex pairs, then source and target vertices. Whitespace may be spaces or line breaks.

Output: Print the shortest distance as one integer, or INF when the target is unreachable. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• V is positive and every vertex index is in the range 0 through V - 1.
• The declared edge count exactly matches the supplied pairs.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Use BFS distances initialized to an unreachable sentinel.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

4 3 0 1 1 2 2 3 0 3

Sample output

3

Why the sample works: Visible walkthrough for the ordinary non-trivial path. BFS assigns a vertex’s minimum hop count at first discovery and leaves disconnected targets unreachable. Input `4 3 0 1 1 2 2 3 0 3` therefore produces `3`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: Mark or assign distance at enqueue time, not at dequeue time.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.