Breadth first search and Eppstein K shortest paths algorithm

Question

I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf

I have trouble particularly with this quote on page 7, paragraph 2.3:

"If G contains cycles, the path tree is infinite. By Lemma 3, the path tree is heap-ordered. However since its degree is not necessarily constant, we cannot directly apply breadth first search (nor Frederickson’s heap selection technique, described later in Lemma 8) to find its k minimum values."

Why can we not use breadth first search (BFS) here? I've tried to look for an answer and to come up with different graphs where the degree of the nodes varies, but so far I do not understand this. Could someone explain how the non-constant degree prevents us from using BFS?

Answer 1

The main reason is that the non-constant degree would imply that the time per result is too high. The number of nodes found by the search, in the end, is going to be k, but all but the last one needs to have their children expanded, so the number of expanded nodes is kd where d is the degree. Unless d is O(1) this will be larger than the eventual time bound of the algorithm.