<p>Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in: 
V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop on Experimental and Efficient Algorithms (WEA ’03), in: Lecture Notes in Computer Science, vol. 2647, Springer, 2003, pp. 179–190.
<a href="https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf</a></p>

CC BY-SA 3.0
2017-08-11T15:51:11.397Z
2017-08-11T15:51:11.397Z
tmn
<p>It's been long enough since I wrote that, that by now my interpretation of what's in there is probably not much more informed than any other reader's. Nevertheless:</p>

<p>I believe that the description you're looking for is the last paragraph of the proof of Lemma 5. Basically, some of the edges in P(G) (the "cross edges") correspond to sidetracks in G (that is, edges that diverge from the shortest path tree). The path in G is formed by following the shortest path tree to the starting vertex of the first sidetrack, following the sidetrack edge itself, following the shortest path tree again to the starting vertex of the next sidetrack, etc.</p>

CC BY-SA 3.0
2011-12-10T23:15:27.053Z
As a side note, this algorithm seems to have been recently outperformed. The details can be found [here](http://www.sciencedirect.com/science/article/pii/S0004370211000865)
Carlos Linares López
CC BY-SA 3.0
2016-05-03T17:37:38.340Z
David, I really need an implementation of your algorithm, best in Java. Can you point me where I can find one?
Tina J
CC BY-SA 3.0
2016-05-03T18:20:17.067Z
The implementations that I know about are linked from the bottom of http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html — but I haven't checked the off-site ones recently so there may be some deadlinks.
David Eppstein
CC BY-SA 3.0
2016-05-04T02:41:43.400Z
Thanks. But more importantly, do you have a complete pseudo-code of your algorithm available somewhere?
Tina J
CC BY-SA 3.0
2016-05-04T02:42:16.120Z
@DavidEppstein Something similar to Dijkstra's one at Wikipedia: https://en.wikipedia.org/wiki/K_shortest_path_routing
Tina J
CC BY-SA 3.0
2016-05-04T04:20:28.423Z
What you've already seen is what you get, sorry.
David Eppstein
CC BY-SA 3.0
2011-12-10T19:07:57.283Z
2011-12-10T19:07:57.283Z
David Eppstein
<p>I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this <a href="http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf" rel="nofollow">paper</a> works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap construction $H(G)$.</p>

<p>So far:</p>

<p>$out(v)$ contains all edges leaving a vertex $v$ in a graph $G$ which are not part of a shortest path in $G$. They are heap-ordered by the "waste of time" called $\delta(e)$ when using this edge instead of the one on a shortest paths. By applying Dijkstra I find the shortest paths to every vertex from $t$.</p>

<p>I can calculate this by taking the length of the edge + (the value of the head vertex (where the directed edge is pointing to) - the value of the tail vertex (where the directed edge is starting). If this is $&gt; 0$ it is not on a shortest path, if it is $= 0$ it is on a shortest path.</p>

<p>Now I build a 2-Min-Heap $H_{out}(v)$ by heapifying the set of edges $out(v)$ according to their $\delta(e)$ for any $v \in V$, where the root $outroot(v)$ has only one child (= subtree). </p>

<p>In order to build $H_T(v)$ I insert $outroot(v)$ in $H_T(next_T(v))$ beginning at the terminal vertex $t$. Everytime a vertex is somehow touched while inserting it is marked with a $*$.</p>

<p>Now I can build $H_G(v)$ by inserting the rest of $H_{out}(w)$ in $H_T(v)$. Every vertex in $H_G(v)$ contains either $2$ children from $H_T(v)$ and $1$ from $H_{out}(w)$ or $0$ from the first and $2$ from the second and is a 3-heap.</p>

<p>With $H_G(v)$ I can build a DAG called $D(G)$ containing a vertex for each $*$-marked vertex from $H_T(v)$ and for each non-root vertex from $H_{out}(v)$.</p>

<p>The roots of $H_G(v)$ in $D(G)$ are called $h(v)$ and they are connected to the vertices they belong to according to $out(v)$ by a "mapping".</p>

<p>So far, so good.</p>

<p>The paper says I can build $P(G)$ by inserting a root $r = r(s)$ and connecting this to $h(s)$ by an inital edge with $\delta(h(s))$. The vertices of $D(G)$ are the same in $P(G)$ but they are not weighted. The edges have lengths. Then for each directed edge $(u,v) \in D(G)$ the corresponding edges in $P(G)$ are created and weighted by $\delta(v) - \delta(u)$. They are called Heap Edges. Then for each vertex $v \in P(G)$, which represents an edge not in a shortest path connecting a pair of vertices $u$ and $w$, "cross edges" are created from $v$ to $h(w)$ in $P(G)$ having a length $\delta(h(w))$. Every vertex in $P(G)$ only has a out going degree of $4$ max.</p>

<p>$P(G)$'s paths starting from $r$ are supposed to be a one-to-one length correspondence between $s$-$t$-paths in $G$. </p>

<p>In the end a new heap ordered 4-Heap $H(G)$ is build. Each vertex corresponds to a path in $P(G)$ rooted at $r$. The parent of any vertex has one fewer edge. The weight of a vertex is the lenght of the corresponding path.</p>

<p>To find the $k$ shortest paths I use BFS to $P(G)$ and "translate" the search result to paths by using $H(G)$.</p>

<p>Unfortunately, I don't understand how I can "read" $P(G)$ and then "translate" it through $H(G)$ to receive the $k$ shortest paths.</p>

CC BY-SA 3.0
2011-12-10T16:56:39.110Z
Did you check the various implementations at http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html ?
Radu GRIGore
<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph><shortest-path>
Finding k shortest Paths with Eppstein's Algorithm
Laura
# Finding k shortest Paths with Eppstein's Algorithm

(Asked by: username_0 on 2011-12-10)

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this [paper](http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf) works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap construction $H(G)$.

So far:

$out(v)$ contains all edges leaving a vertex $v$ in a graph $G$ which are not part of a shortest path in $G$. They are heap-ordered by the "waste of time" called $\delta(e)$ when using this edge instead of the one on a shortest paths. By applying Dijkstra I find the shortest paths to every vertex from $t$.

I can calculate this by taking the length of the edge + (the value of the head vertex (where the directed edge is pointing to) - the value of the tail vertex (where the directed edge is starting). If this is $> 0$ it is not on a shortest path, if it is $= 0$ it is on a shortest path.

Now I build a 2-Min-Heap $H\_{out}(v)$ by heapifying the set of edges $out(v)$ according to their $\delta(e)$ for any $v \in V$, where the root $outroot(v)$ has only one child (= subtree).

In order to build $H\_T(v)$ I insert $outroot(v)$ in $H\_T(next\_T(v))$ beginning at the terminal vertex $t$. Everytime a vertex is somehow touched while inserting it is marked with a $\*$.

Now I can build $H\_G(v)$ by inserting the rest of $H\_{out}(w)$ in $H\_T(v)$. Every vertex in $H\_G(v)$ contains either $2$ children from $H\_T(v)$ and $1$ from $H\_{out}(w)$ or $0$ from the first and $2$ from the second and is a 3-heap.

With $H\_G(v)$ I can build a DAG called $D(G)$ containing a vertex for each $\*$-marked vertex from $H\_T(v)$ and for each non-root vertex from $H\_{out}(v)$.

The roots of $H\_G(v)$ in $D(G)$ are called $h(v)$ and they are connected to the vertices they belong to according to $out(v)$ by a "mapping".

So far, so good.

The paper says I can build $P(G)$ by inserting a root $r = r(s)$ and connecting this to $h(s)$ by an inital edge with $\delta(h(s))$. The vertices of $D(G)$ are the same in $P(G)$ but they are not weighted. The edges have lengths. Then for each directed edge $(u,v) \in D(G)$ the corresponding edges in $P(G)$ are created and weighted by $\delta(v) - \delta(u)$. They are called Heap Edges. Then for each vertex $v \in P(G)$, which represents an edge not in a shortest path connecting a pair of vertices $u$ and $w$, "cross edges" are created from $v$ to $h(w)$ in $P(G)$ having a length $\delta(h(w))$. Every vertex in $P(G)$ only has a out going degree of $4$ max.

$P(G)$'s paths starting from $r$ are supposed to be a one-to-one length correspondence between $s$-$t$-paths in $G$.

In the end a new heap ordered 4-Heap $H(G)$ is build. Each vertex corresponds to a path in $P(G)$ rooted at $r$. The parent of any vertex has one fewer edge. The weight of a vertex is the lenght of the corresponding path.

To find the $k$ shortest paths I use BFS to $P(G)$ and "translate" the search result to paths by using $H(G)$.

Unfortunately, I don't understand how I can "read" $P(G)$ and then "translate" it through $H(G)$ to receive the $k$ shortest paths.

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

> **Comments:**
> **username_1**: Did you check the various implementations at http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html ?  

---

## 2 answers

### Answer by username_3 on 2011-12-10. Score: 25 | Accepted answer

It's been long enough since I wrote that, that by now my interpretation of what's in there is probably not much more informed than any other reader's. Nevertheless:

I believe that the description you're looking for is the last paragraph of the proof of Lemma 5. Basically, some of the edges in P(G) (the "cross edges") correspond to sidetracks in G (that is, edges that diverge from the shortest path tree). The path in G is formed by following the shortest path tree to the starting vertex of the first sidetrack, following the sidetrack edge itself, following the shortest path tree again to the starting vertex of the next sidetrack, etc.

> **Comments:**
> **username_4**: As a side note, this algorithm seems to have been recently outperformed. The details can be found [here](http://www.sciencedirect.com/science/article/pii/S0004370211000865)  
> **username_5**: David, I really need an implementation of your algorithm, best in Java. Can you point me where I can find one?  
> **username_3**: The implementations that I know about are linked from the bottom of http://www.ics.uci.edu/~eppstein/pubs/p-kpath.html — but I haven't checked the off-site ones recently so there may be some deadlinks.  
> **username_5**: Thanks. But more importantly, do you have a complete pseudo-code of your algorithm available somewhere?  
> **username_5**: @DavidEppstein Something similar to Dijkstra's one at Wikipedia: https://en.wikipedia.org/wiki/K_shortest_path_routing  
> **username_3**: What you've already seen is what you get, sorry.  

---

### Answer by username_2 on 2017-08-11. Score: 4

Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in:
V.M. Jiménez, A. Marzal, A lazy version of Eppstein’s shortest paths algorithm, in: 2nd International Workshop on Experimental and Efficient Algorithms (WEA ’03), in: Lecture Notes in Computer Science, vol. 2647, Springer, 2003, pp. 179–190.
<https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf>


---

