# Shortest path in unweighted graph using an iterator only

I want to find the shortest path (least number of edges) between two nodes in an unweighted graph.

How do I implement this by using a BFSiterator(v) which returns vertices in BFS order, starting from node v? The graph interface only allows the function neighbours(v) (to get the neighbour vertices of v) to be used. This was a homework exercise long ago, but I couldn't find an answer.

I am kind of stuck since I am not sure how to detect when a new level in the graph is reached, since the BFS iterator only return vertices. Simply collecting all vertices from the start to end node in BFS order does not work, since this would contain sibling vertices as well which are not on the shortest path.

• You should "mark" the nodes in order to detect if they are visited before or not. I am not sure if this is what you ask. Maybe I can help more if you state the question in a formal way. What is the purpose of BFSiterator? What does neighbours return? etc – padawan Nov 10 '16 at 12:14
• BFSiterator(v) implements an Iterator<Vertex> which returns vertices of the graph in BFS order, traversed from v. neighbours(v) returns a Collection<Vertex> of direct neighbours of the given vertex v. – Laurens Nov 10 '16 at 12:17