Znajdowanie k najkrótszych ścieżek za pomocą algorytmu Eppsteina

Próbuję dowiedzieć się, jak działa wykres ścieżki według algorytmu Eppsteina w tym artykule i jak mogę zrekonstruować najkrótszych ścieżek od do z odpowiednią konstrukcją stosu .k s t H ( G $P(G)$$k$$s$$t$$H(G)$

Jak dotąd:

$out(v)$ zawiera wszystkie krawędzie opuszczające wierzchołek na wykresie , które nie są częścią najkrótszej ścieżce . Są one uporządkowane według „straty czasu” zwanej gdy używa się tej krawędzi zamiast krawędzi na najkrótszych ścieżkach. Stosując Dijkstra, znajduję najkrótsze ścieżki do każdego wierzchołka od .G G δ ( e ) $v$$G$$G$$\delta(e)$$t$

Mogę to obliczyć, biorąc długość krawędzi + (wartość wierzchołka głowy (gdzie skierowana jest skierowana krawędź) - wartość wierzchołka ogona (gdzie zaczyna się skierowana krawędź). Jeśli jest to to nie znajduje się na najkrótszej ścieżce, jeśli jest , znajduje się na najkrótszej ścieżce.= $> 0$$= 0$

Teraz buduję 2-Min-Heap poprzez gromadzenie zbioru krawędzi zgodnie z ich dla dowolnego , gdzie root ma tylko jedno dziecko (= poddrzewo).o u t ( v ) δ ( e ) v ∈ V o u t r o o t ( v $H_{out}(v)$$out(v)$$\delta(e)$$v \in V$$outroot(v)$

Aby zbudować wstawiam w zaczynając od wierzchołka terminalu . Za każdym razem, gdy wierzchołek jest dotykany podczas wstawiania, jest oznaczony .o u t r o o t ( v ) H T ( n e x t T ( v ) ) t $H_T(v)$$outroot(v)$$H_T(next_T(v))$$t$$*$

Teraz mogę zbudować , wstawiając resztę w . Każdy wierzchołek w zawiera albo dzieci z i z lub z pierwszego i z drugiego i jest 3-stertą.H o u t ( w ) H T ( v ) H G ( v ) 2 H T ( v ) 1 H o u t ( w ) 0 $H_G(v)$$H_{out}(w)$$H_T(v)$$H_G(v)$$2$$H_T(v)$$1$$H_{out}(w)$$0$$2$

Za pomocą mogę zbudować DAG o nazwie zawierający wierzchołek dla każdego wierzchołka oznaczonego * z H_T (v) i dla każdego wierzchołka innego niż root z H_ {out} (v) .D ( G ) ∗ H T ( v ) H o u t ( v $H_G(v)$$D(G)$$*$$H_T(v)$$H_{out}(v)$

Pierwiastki $H_G(v)$ w $D(G)$ są nazywane $h(v)$ i są połączone z wierzchołkami, do których należą, zgodnie z $out(v)$ poprzez „mapowanie”.

Jak na razie dobrze.

Artykuł mówi, że mogę zbudować $P(G)$ , wstawiając pierwiastek $r = r(s)$ i łącząc go z $h(s)$ za pomocą początkowej krawędzi za pomocą $\delta(h(s))$ . Wierzchołki $D(G)$ są takie same w $P(G)$ ale nie są ważone. Krawędzie mają długości. Następnie dla każdej skierowanej krawędzi $(u,v) \in D(G)$ odpowiednie krawędzie w $P(G)$ są tworzone i ważone przez $\delta(v) - \delta(u)$ . Są to tak zwane brzegi sterty. Następnie dla każdego wierzchołka $v \in P(G)$ , który reprezentuje krawędź nie w najkrótszej ścieżce łączącej parę wierzchołków $u$ i $w$ , tworzone są „krawędzie poprzeczne” z$v$ do $h(w)$ w $P(G)$ o długości $\delta(h(w))$ . Każdy wierzchołek w $P(G)$ ma tylko wychodzący stopień $4$ maks.

$P(G)$ „s drogi już od $r$ mają być długość korespondencji jeden-do-jednego między $s$ - $t$ , ścieżek w $G$ .

Na koniec budowana jest nowa sterta 4-sterty $H(G)$ . Każdy wierzchołek odpowiada ścieżce w $P(G)$ zakorzenionej w $r$ . Element nadrzędny dowolnego wierzchołka ma jedną krawędź mniejszą. Ciężar wierzchołka to długość odpowiedniej ścieżki.

Aby znaleźć najkrótszych ścieżek, używam BFS na i „tłumaczę” wynik wyszukiwania na ścieżki za pomocą .$k$$P(G)$$H(G)$

Niestety nie rozumiem, jak mogę „odczytać” a następnie „przetłumaczyć” go przez aby otrzymać najkrótszych ścieżek.$P(G)$$H(G)$$k$

Minęło już wystarczająco dużo czasu, odkąd to napisałem, że moja interpretacja tego, co tam jest, prawdopodobnie nie jest dużo lepiej poinformowana niż jakikolwiek inny czytelnik. Niemniej jednak:

Uważam, że opis, którego szukasz, jest ostatnim akapitem dowodu na Lemat 5. Zasadniczo niektóre krawędzie w P (G) („krawędzie poprzeczne”) odpowiadają bocznym ścieżkom w G (to znaczy krawędziom, które odejdź od najkrótszego drzewa ścieżki). Ścieżka w G jest tworzona przez podążanie najkrótszym drzewem ścieżki do początkowego wierzchołka pierwszego bocznego toru, podążając za samą krawędzią boczną, ponownie podążając za najkrótszą drzewem ścieżki do początkowego wierzchołka następnej bocznej ścieżki itp.

Pseudokod algorytmu Eppsteina (i jego leniwa wersja) podano w: VM Jiménez, A. Marzal, Leniwa wersja algorytmu najkrótszych ścieżek Eppsteina, w: 2. Międzynarodowym warsztacie na temat algorytmów eksperymentalnych i efektywnych (WEA '03), w: Wykłady z informatyki, vol. 2647, Springer, 2003, s. 179–190. https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf