Trouver k chemins les plus courts avec l'algorithme d'Eppstein

J'essaie de comprendre comment fonctionne le graphique de chemin selon l'algorithme d'Eppstein dans cet article et comment je peux reconstruire les k chemins les plus courts de s à t avec la construction de tas correspondante H ( G $P(G)$$k$$s$$t$$H(G)$ .

Jusque là:

contient tousbordslaissant un sommet v d'un graphe G qui ne font pas partie d'un plus court chemin dans G . Ils sont classés par tas par la «perte de temps» appelée δ ( e ) lors de l'utilisation de cette arête au lieu de celle sur un des chemins les plus courts. En appliquant Dijkstra, je trouve les chemins les plus courts vers chaque sommet de t .$out(v)$$v$$G$$G$$\delta(e)$$t$

Je peux calculer cela en prenant la longueur du bord + (la valeur du sommet de la tête (où pointe le bord dirigé)) - la valeur du sommet de la queue (où commence le bord dirigé). Si c'est il n'est pas sur un chemin le plus court, s'il est = 0, il est sur un chemin le plus court.$> 0$$= 0$

Maintenant , je construire un 2-Min-Heap par heapifying l'ensemble des arêtes o u t ( v ) en fonction de leur δ ( e ) pour chaque v ∈ V , où la racine o u t r o o t ( v ) n'a qu'un seul enfant (= sous-arbre).$H_{out}(v)$$out(v)$$\delta(e)$$v \in V$$outroot(v)$

Afin de construire j'insère o u t r o o t ( v ) dans H T ( n e x t T ( v ) ) en commençant au sommet terminal t . Chaque fois qu'un sommet est touché d'une manière ou d'une autre lors de son insertion, il est marqué d'un ∗ .$H_T(v)$$outroot(v)$$H_T(next_T(v))$$t$$*$

Maintenant, je peux construire en insérant le reste de H o u t ( w ) dans H T ( v ) . Chaque sommet dans H G ( v ) contient soit 2 enfants de H T ( v ) et 1 de H o u t ( w ) ou 0 du premier et 2 du second et est un 3 tas.$H_G(v)$$H_{out}(w)$$H_T(v)$$H_G(v)$$2$$H_T(v)$$1$$H_{out}(w)$$0$$2$

Avec je peux construire un DAG appelé D ( G ) contenant un sommet pour chaque sommet marqué ∗ de H T ( v ) et pour chaque sommet non racine de H o u t ( v ) .$H_G(v)$$D(G)$$*$$H_T(v)$$H_{out}(v)$

Les racines de dans D ( G ) sont appelées h ( v ) et elles sont reliées aux sommets auxquels elles appartiennent selon o u t ( v ) par un "mapping".$H_G(v)$$D(G)$$h(v)$$out(v)$

Jusqu'ici tout va bien.

L'article dit que je peux construire en insérant une racine r = r ( s ) et en la connectant à h ( s ) par un bord initial avec δ ( h ( s ) ) . Les sommets de D ( G ) sont les mêmes dans P ( G ) mais ils ne sont pas pondérés. Les bords ont des longueurs. Puis pour chaque bord dirigé ( u , v ) ∈ D ( G $P(G)$$r = r(s)$$h(s)$$\delta(h(s))$$D(G)$$P(G)$$(u,v) \in D(G)$les arêtes correspondantes dans sont créées et pondérées par δ ( v ) - δ ( u ) . Ils sont appelés Heap Edges. Ensuite, pour chaque sommet v ∈ P ( G ) , qui représente une arête qui n'est pas dans un chemin le plus court reliant une paire de sommets u et w , des "arêtes croisées" sont créées de v à h ( w ) dans P ( G ) ayant une longueur δ ( h ( $P(G)$$\delta(v) - \delta(u)$$v \in P(G)$$u$$w$$v$$h(w)$$P(G)$ . Chaque sommet de P ( G ) a seulement un degré sortant de 4 max.$\delta(h(w))$$P(G)$$4$

les chemins de »partir de r sont censés être un-à-un entrelongueur correspondance s - t -paths dans G .$P(G)$$r$$s$$t$$G$

À la fin, un nouveau tas ordonné 4-Heap est construit. Chaque sommet correspond à un chemin en P ( G ) enraciné en r . Le parent d'un sommet a un bord de moins. Le poids d'un sommet est la longueur du chemin correspondant.$H(G)$$P(G)$$r$

Pour trouver les chemins les plus courts, j'utilise BFS en P ( G ) et "traduire" le résultat de la recherche en chemins en utilisant H ( G ) .$k$$P(G)$$H(G)$

Malheureusement, je ne comprends pas comment je peux "lire" puis le "traduire" par H ( G ) pour recevoir les k chemins les plus courts.$P(G)$$H(G)$$k$

Cela fait assez longtemps depuis que j'ai écrit cela, que maintenant mon interprétation de ce qui s'y trouve n'est probablement pas beaucoup plus informée que n'importe quel autre lecteur. Cependant:

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.

Le pseudocode de l'algorithme d'Eppstein (et sa version paresseuse des auteurs) est donné dans: VM Jiménez, A. Marzal, Une version paresseuse de l'algorithme des chemins les plus courts d'Eppstein, dans: 2nd International Workshop on Experimental and Efficient Algorithms (WEA '03), dans: Lecture Notes in Computer Science, vol. 2647, Springer, 2003, p. 179-190. https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf