<p>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.</p>

CC BY-SA 3.0
2013-03-27T16:50:31.403Z
2013-03-27T16:50:31.403Z
David Eppstein
<p>I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf" rel="nofollow">http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf</a></p>

<p>I have trouble particularly with this quote on page 7, paragraph 2.3:</p>

<p>"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."</p>

<p>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?</p>

<graph-theory><graph-algorithms><ds.data-structures><directed-acyclic-graph><shortest-path>
Breadth first search and Eppstein K shortest paths algorithm
zenperttu
# Breadth first search and Eppstein K shortest paths algorithm

(Asked by: username_0 on 2013-03-27)

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?

**Tags:** graph-theory, graph-algorithms, ds.data-structures, directed-acyclic-graph, shortest-path

---

## 1 answers

### Answer by username_1 on 2013-03-27. Score: 5 | Accepted answer

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.


---

