Mit Eppsteins Algorithmus k kürzeste Wege finden

Ich versuche herauszufinden, wie der Pfadgraph nach Eppsteins Algorithmus in dieser Arbeit funktioniert und wie ich die kürzesten Pfade von nach mit der entsprechenden Heapkonstruktion rekonstruieren kann . $P(G)$ $k$ $s$ $t$ $H(G)$

Bisher:

$out(v)$ enthält alle Kanten, die einen Eckpunkt in einem Graphen hinterlassen und nicht Teil eines kürzesten Pfades in . Sie sind durch die "Zeitverschwendung", die als wird, haufenweise geordnet, wenn diese Kante anstelle der Kante auf kürzesten Wegen verwendet wird. Durch Anwenden von Dijkstra finde ich die kürzesten Pfade zu jedem Scheitelpunkt von . $v$ $G$ $G$ $\delta(e)$ $t$

Ich kann dies berechnen, indem ich die Länge der Kante + (den Wert des Kopfscheitelpunkts (auf den die gerichtete Kante zeigt) - den Wert des Schwanzscheitelpunkts (auf den die gerichtete Kante beginnt) nehme. Wenn dies es ist nicht auf dem kürzesten Weg, wenn es , ist es auf dem kürzesten Weg. $> 0$ $= 0$

Jetzt baue ich einen 2-Min-Heap indem ich die Menge der Kanten entsprechend ihrem für ein beliebiges , wobei die Wurzel nur hat ein Kind (= Teilbaum). $H_{out}(v)$ $out(v)$ $\delta(e)$ $v \in V$ $outroot(v)$

Um zu bilden, ich in beginnend am . Jedes Mal, wenn ein Scheitelpunkt beim Einfügen berührt wird, wird er mit einem markiert . $H_T(v)$ $outroot(v)$ $H_T(next_T(v))$ $t$ $*$

Jetzt kann ich indem ich den Rest von in . Jeder Eckpunkt in enthält entweder Kinder aus und aus oder aus dem ersten und aus dem zweiten und ist ein 3-Haufen. $H_G(v)$ $H_{out}(w)$ $H_T(v)$ $H_G(v)$ $2$ $H_T(v)$ $1$ $H_{out}(w)$ $0$ $2$

Mit kann ich eine DAG mit dem Namen erstellen, die einen Vertex für jeden mit markierten Vertex aus und für jeden Nicht-Wurzel-Vertex aus . $H_G(v)$ $D(G)$ $*$ $H_T(v)$ $H_{out}(v)$

Die Wurzeln von in heißen und sind durch eine "Abbildung" mit den Scheitelpunkten verbunden, zu denen sie gemäß gehören . $H_G(v)$ $D(G)$ $h(v)$ $out(v)$

So weit, ist es gut.

Das Papier sagt I bauen kann durch Einführen eine Wurzel und Verbinden dies zu durch eine Kante mit inital . Die Eckpunkte von sind die gleichen wie in , sie werden jedoch nicht gewichtet. Die Kanten haben Längen. Dann werden für jede gerichtete Kante die entsprechenden Kanten in erzeugt und mit gewichtet . Sie heißen Heap Edges. Dann werden für jeden Scheitelpunkt , der eine Kante darstellt, die sich nicht auf dem kürzesten Weg befindet und ein Paar von Scheitelpunkten und , "Kreuzkanten" aus erzeugt $P(G)$ $r = r(s)$ $h(s)$ $\delta(h(s))$ $D(G)$ $P(G)$ $(u,v) \in D(G)$ $P(G)$ $\delta(v) - \delta(u)$ $v \in P(G)$ $u$ $w$ $v$ bis in mit einer Länge . Jeder Eckpunkt in nur einen Ausgangsgrad von max. . $h(w)$ $P(G)$ $\delta(h(w))$ $P(G)$ $4$

$P(G)$ ‚s Pfade von Ausgang sollen eine Eins-zu-Eins - Entsprechung zwischen Länge seiner - -paths in . $r$ $s$ $t$ $G$

Am Ende wird ein neuer, bestellter 4-Heap gebaut. Jeder Eckpunkt entspricht einem Pfad in , der bei verwurzelt ist . Das übergeordnete Element eines beliebigen Scheitelpunkts hat eine Kante weniger. Das Gewicht eines Scheitelpunkts ist die Länge des entsprechenden Pfades. $H(G)$ $P(G)$ $r$

Um die kürzesten Pfade zu finden, verwende ich BFS zu und "übersetze" das Suchergebnis mit in Pfade . $k$ $P(G)$ $H(G)$

Leider verstehe ich nicht, wie ich "lesen" und dann durch "übersetzen" kann , um die kürzesten Wege zu erhalten. $P(G)$ $H(G)$ $k$

ds.algorithms graph-theory graph-algorithms directed-acyclic-graph Laura
quelle

Haben Sie die verschiedenen Implementierungen unter ics.uci.edu/~eppstein/pubs/p-kpath.html überprüft ?

Radu GRIGore

Antworten:

Es ist lange genug her, dass ich geschrieben habe, dass meine Interpretation dessen, was darin enthalten ist, wahrscheinlich nicht viel informierter ist als die anderer Leser. Dennoch:

Ich glaube, dass die Beschreibung, nach der Sie suchen, der letzte Absatz des Beweises von Lemma 5 ist. Grundsätzlich entsprechen einige der Kanten in P (G) (die "Querkanten") Ablenkungsspuren in G (dh Kanten, die vom Baum des kürzesten Pfades abweichen). Der Pfad in G wird gebildet, indem dem Baum mit dem kürzesten Pfad zum Startknoten des ersten Nebengleises gefolgt wird, der Kante des Nebengleises selbst gefolgt wird, dem Baum mit dem kürzesten Pfad erneut zum Startknoten des nächsten Nebengleises gefolgt wird usw.

David Eppstein
quelle

Als Randnotiz scheint dieser Algorithmus in letzter Zeit übertroffen worden zu sein. Die Details finden Sie hier

Carlos Linares López

David, ich brauche wirklich eine Implementierung Ihres Algorithmus, am besten in Java. Können Sie mir zeigen, wo ich einen finden kann?

Tina J

Die Implementierungen, von denen ich weiß, sind am Ende von ics.uci.edu/~eppstein/pubs/p-kpath.html verlinkt - aber ich habe die Off-Site- Implementierungen in letzter Zeit nicht überprüft, so dass es möglicherweise einige Deadlinks gibt.

David Eppstein

Vielen Dank. Aber was noch wichtiger ist: Haben Sie irgendwo einen vollständigen Pseudocode Ihres Algorithmus zur Verfügung?

Tina J

@DavidEppstein Ähnliches wie Dijkstra bei Wikipedia: en.wikipedia.org/wiki/K_shortest_path_routing

Tina J

Pseudocode für Eppsteins Algorithmus (und die Lazy-Version der Autoren) finden Sie in: VM Jiménez, A. Marzal, Eine Lazy-Version von Eppsteins Algorithmus für kürzeste Wege, in: 2. Internationaler Workshop zu experimentellen und effizienten Algorithmen (WEA '03), in: Lecture Notes in Computer Science, vol. 2647, Springer, 2003, S. 179–190. https://pdfs.semanticscholar.org/3a31/5a14a2fc773d2d800186121905016de31705.pdf

tmn
quelle