Encontrar k caminos más cortos con el algoritmo de Eppstein

Estoy tratando de descubrir cómo funciona el Gráfico de ruta $P(G)$ según el Algoritmo de Eppstein en este documento y cómo puedo reconstruir las $k$ rutas más cortas de a con la construcción del montón .$s$$t$$H(G)$

Hasta aquí:

v G $out(v)$ contiene todos los bordes dejando un vértice en un gráfico de que no son parte de un camino más corto en . Están ordenados en montón por la "pérdida de tiempo" llamada δ ( e ) cuando se usa este borde en lugar del que está en los caminos más cortos. Al aplicar Dijkstra, encuentro los caminos más cortos para cada vértice desde t .$v$$G$$G$$\delta(e)$$t$

Puedo calcular esto tomando la longitud del borde + (el valor del vértice de la cabeza (donde apunta el borde dirigido) - el valor del vértice de la cola (donde comienza el borde dirigido). Si es $> 0$ , no está en la ruta más corta, si es $= 0$ está en la ruta más corta.

Ahora construyo un 2-Min-Heap $H_{out}(v)$ al heapificar el conjunto de aristas $out(v)$ acuerdo con su $\delta(e)$ para cualquier $v \in V$ , donde la raíz $outroot(v)$ tiene solo un hijo (= subárbol).

Para construir inserto o u t r o o t ( v ) en H T ( $H_T(v)$$outroot(v)$ comenzando en el vértice terminal t . Cada vez que se toca un vértice de alguna manera al insertarlo, se marca con una ∗ .$H_T(next_T(v))$$t$$*$

Ahora puedo construir insertando el resto de H o u t ( w ) en H T ( v ) . Cada vértice en H G ( v ) contiene 2 hijos de H T ( v ) y 1 de H o u t ( w ) o 0 del primero y 2 del segundo y es un montón de 3.$H_G(v)$$H_{out}(w)$$H_T(v)$$H_G(v)$$2$$H_T(v)$$1$$H_{out}(w)$$0$$2$

Con puedo construir un DAG llamado D ( G ) que contiene un vértice para cada vértice marcado con ∗ de H T ( v ) y para cada vértice no raíz de H o u t ( v ) .$H_G(v)$$D(G)$$*$$H_T(v)$$H_{out}(v)$

Las raíces de en D ( G ) se llaman h ( v ) y están conectadas a los vértices a los que pertenecen según o u t ( v ) mediante un "mapeo".$H_G(v)$$D(G)$$h(v)$$out(v)$

Hasta aquí todo bien.

El documento dice que puedo construir insertando una raíz r = r ( s ) y conectando esto a h ( s ) por un borde inicial con δ ( h ( s ) ) . Los vértices de D ( G ) son los mismos en P ( G ) pero no están ponderados. Los bordes tienen longitudes. Luego, para cada borde dirigido ( u , v ) ∈ D ( G $P(G)$$r = r(s)$$h(s)$$\delta(h(s))$$D(G)$$P(G)$$(u,v) \in D(G)$los bordes correspondientes en se crean y se ponderan con δ ( v ) - δ ( u ) . Se llaman Heap Edges. Luego, para cada vértice v ∈ P ( G ) , que representa un borde que no está en el camino más corto que conecta un par de vértices u y w , se crean "bordes transversales" de v a h ( w ) en P ( G ) que tiene una longitud δ ( h ( $P(G)$$\delta(v) - \delta(u)$$v \in P(G)$$u$$w$$v$$h(w)$$P(G)$ . Cada vértice en P ( G ) solo tiene un grado de salida de 4 máx.$\delta(h(w))$$P(G)$$4$

caminos 's a partir de r se supone que son una correspondencia longitud uno-a-uno entre s - t -vías en G .$P(G)$$r$$s$$t$$G$

Al final, se construye un nuevo montón ordenado 4-Heap . Cada vértice corresponde a una ruta en P ( G ) enraizada en r . El padre de cualquier vértice tiene un borde menos. El peso de un vértice es la longitud de la ruta correspondiente.$H(G)$$P(G)$$r$

Para encontrar las rutas más cortas, uso BFS a P ( G ) y "traduzco" el resultado de la búsqueda a rutas usando H ( G ) .$k$$P(G)$$H(G)$

Desafortunadamente, no entiendo cómo puedo "leer" y luego "traducirlo" a través de H ( G ) para recibir las k rutas más cortas.$P(G)$$H(G)$$k$

Ha pasado bastante tiempo desde que escribí eso, que por ahora mi interpretación de lo que hay allí probablemente no esté mucho más informada que la de cualquier otro lector. Sin embargo:

Creo que la descripción que está buscando es el último párrafo de la prueba del Lema 5. Básicamente, algunos de los bordes en P (G) (los "bordes cruzados") corresponden a las vías laterales en G (es decir, bordes que divergen del árbol del camino más corto). La ruta en G se forma siguiendo el árbol de ruta más corta hasta el vértice inicial de la primera pista lateral, siguiendo el borde de la misma, siguiendo el árbol de ruta más corta nuevamente hasta el vértice inicial de la siguiente pista lateral, etc.

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