Нахождение k кратчайших путей с помощью алгоритма Эппштейна

Я пытаюсь выяснить, как граф путей соответствии с алгоритмом Эппштейна в этой статье работает, и как я могу восстановить k кратчайших путей от s до t с соответствующей конструкцией кучи H ( G ) .$P(G)$$k$$s$$t$$H(G)$

Слишком далеко:

содержит все ребраоставляя вершину V в графе G , которые не являются частью кратчайшего пути в G . Они упорядочены в куче за счет «траты времени», называемой δ ( e ), при использовании этого ребра, а не на кратчайших путях. Применяя Дейкстру, я нахожу кратчайшие пути к каждой вершине из t .$out(v)$$v$$G$$G$$\delta(e)$$t$

Я могу рассчитать это, взяв длину ребра + (значение вершины головы (на которое указывает направленный край) - значение вершины хвоста (где начинается направленный край). Если это это не на кратчайшем пути, если = 0, то на кратчайшем пути.$> 0$$= 0$

Теперь я строю 2-мин-кучу , накапливая множество ребер o u t ( v ) в соответствии с их δ ( e ) для любого v ∈ V , где корень o u t r $H_{out}(v)$$out(v)$$\delta(e)$$v \in V$ есть только один дочерний элемент (= поддерево).$outroot(v)$

Для того чтобы построить я Вкладыш о у т т о о т ( V ) в Н Т ( п е х т Т ( v ) ) , начиная с вершины терминала т . Каждый раз, когда при вставке к вершине как-то дотрагиваются, она помечается знаком ∗ .$H_T(v)$$outroot(v)$$H_T(next_T(v))$$t$$*$

Теперь я могу построить , вставив оставшуюся часть H o u t ( w ) в H T ( v ) . Каждая вершина в H G ( v ) содержит либо 2 детей из H T ( v ) и 1 из H o u t ( w ), либо 0 из первого и 2 из второго и представляет собой 3-кучу.$H_G(v)$$H_{out}(w)$$H_T(v)$$H_G(v)$$2$$H_T(v)$$1$$H_{out}(w)$$0$$2$

С помощью я могу построить DAG с именем D ( G ), содержащую вершину для каждой ∗ -отмеченной вершины из H T ( v ) и для любой некорневой вершины из H o u t ( v ) .$H_G(v)$$D(G)$$*$$H_T(v)$$H_{out}(v)$

Корни в D ( G ) называются h ( v ) и связаны с вершинами, которым они принадлежат, согласно o u t ( v ) посредством «отображения».$H_G(v)$$D(G)$$h(v)$$out(v)$

Все идет нормально.

В статье говорится, что я могу построить , вставив корень r = r ( s ) и соединив его с h ( s ) начальным ребром с δ ( h ( s ) ) . Вершины D ( G ) одинаковы в P ( G ), но они не взвешены. Края имеют длину. Тогда для каждого направленного ребра ( u , v ) ∈ D ( G $P(G)$$r = r(s)$$h(s)$$\delta(h(s))$$D(G)$$P(G)$$(u,v) \in D(G)$ соответствующие ребра в создаются и взвешиваются по δ ( v ) - δ ( u ) . Их называют кучей краев. Тогда для каждой вершины v ∈ P ( G ) , представляющей ребро, не входящее в кратчайший путь, соединяющий пару вершин u и w , создаются «поперечные ребра» из v в h ( w ) в P ( G ), имеющие длину δ ( ч ( $P(G)$$\delta(v) - \delta(u)$$v \in P(G)$$u$$w$$v$$h(w)$$P(G)$ . Каждая вершина в P ( G $\delta(h(w))$$P(G)$ только имеет выходную степень $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.

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.

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