Shortest paths that are impossible for BFS to find?

Question

I took an exam earlier and there was a question that baffled me and everyone else I talked to. It asked the following:

Give an example of an unweighted graph G and two vertices s and f such that there is a shortest path between s and f that breadth-first search (beginning at s) will never find, regardless of the order it visits the vertices adjacent to a particular edge.

To us, this seems impossible. My first thought was that if a shortest path contained a vertex as its nth step that could be reached in m steps from s, where m<n, then that path will never be found by BFS because the vertex will have already been marked as visited. But if that were the case, said path would not be a shortest path at all, since there would be a shorter path obtained by getting to the vertex in m steps and then continuing on as normal.

Did our professor pose an impossible question (perhaps as a typo), or am I missing something?

EDIT: To clear up any possible ambiguity, the question does not ask to give an example where BFS fails to find a shortest path from s to f. Rather, it asks to give an example where there exists some shortest path from s to f that BFS will never find. So the fact that BFS is complete and optimal alone does not preclude this possibility, unless I misunderstand the meaning of the terms.

EDIT 2: It may be assumed also that the BFS algorithm we are working with will not process the same node twice. See, for example, the algorithm outline on the BFS Wiki.

Answer 1

The Example

Let G = (V,E) a graph with V = ℕ ∪ {-1, 0} and E = { {-1,t}, {t,0} | t ∈ ℕ }
and let s = -1 and f = 0. There exist an infinite number of paths of length 2 from s to f, but since s has an infinite number of neighbors, BFS will never come to f.

No finite examples possible

There exists no finite graph, such that BFS does not find the shortest path from s to f. Lets say G is a finite graph and s = a₀ → a₁ → ... → an → an+1 = f is a shortest path from s to f. Then exist an execution order of BFS that looks like this:

For all i from 0 to n visit ai+1 first and then all other direct neighbors of ai.

Since G is a finite graph there exist also only finite many direct neighbors of each node ai. So it will finish the listing and come to the next node on the path. Since the path is a shortest one, it is the first one that is found to connect s and f. So there cannot exist a finite graph such that BFS does not find the shortest path from s to f.

Paths cannot be shorter than two edges

There can also be no example with a path from s to f shorter than 2.
The shortest path one can think of would be of length 1, if s and f are considered not to be the same node. But this means that f is an direct neighbor of s and so there exists a BFS that visits f first and after that goes on with the infinite number of other neighbors.

Answer 2

I think @hexaflexagonal might have stated the problem wrongly.

It should be a problem in CLRS:

the problem and the solution:

Because of the nature of BFS, there are some sets of E_{\pi} won't be produced by BFS. This is the case for the cyclic graph with multiple shortest-path solutions.