16
$\begingroup$

I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper 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.

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ As a side note, this algorithm seems to have been recently outperformed. The details can be found here $\endgroup$ – Carlos Linares López Dec 10 '11 at 23:15
  • $\begingroup$ David, I really need an implementation of your algorithm, best in Java. Can you point me where I can find one? $\endgroup$ – Tina J May 3 '16 at 17:37
  • 1
    $\begingroup$ The implementations that I know about are linked from the bottom of ics.uci.edu/~eppstein/pubs/p-kpath.html — but I haven't checked the off-site ones recently so there may be some deadlinks. $\endgroup$ – David Eppstein May 3 '16 at 18:20
  • $\begingroup$ Thanks. But more importantly, do you have a complete pseudo-code of your algorithm available somewhere? $\endgroup$ – Tina J May 4 '16 at 2:41
  • $\begingroup$ @DavidEppstein Something similar to Dijkstra's one at Wikipedia: en.wikipedia.org/wiki/K_shortest_path_routing $\endgroup$ – Tina J May 4 '16 at 2:42
4
$\begingroup$

Pseudocode for Eppstein's algorithm (and the authors' lazy version of it) are given in: V.M. Jimé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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.