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