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.
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
.
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
from0
ton
visitai+1
first and then all other direct neighbors ofai
.
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
.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With