THINK FIRST·CODE LATER

← All labs

Fewest hops: BFS shortest path

Problem

Read an undirected, unweighted graph and two vertices s and t, and print a path from s to t with the fewest edges.

Input

n m          // vertices 0 .. n-1, number of edges
u1 v1        // m lines, one undirected edge each (in any order)
...
s t

Rules

  • Build adjacency lists and sort each list in increasing order; run BFS from s, visiting neighbours in that order.
  • A vertex's parent is the vertex it was first discovered from. This makes the path unique when several shortest paths exist.

Output — if t is reachable:

Distance: 3
Path: 0 -> 5 -> 2 -> 7

If t is not reachable, print exactly No path. When s = t the answer is Distance: 0 and Path: s.

Example input for the output above:

8 10
5 4
0 3
6 7
3 1
0 5
2 7
5 2
1 6
4 6
3 4
0 7

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d15-1-data-1.txt

8 10
5 4
0 3
6 7
3 1
0 5
2 7
5 2
1 6
4 6
3 4
0 7
What your program must print for d15-1-data-1.txt
Distance: 3
Path: 0 -> 5 -> 2 -> 7

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d15-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content d15-1-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.