Eppsteins Algorithmus und Yens Algorithmus für k kürzeste Wege

Question

Ich versuche genau zu verstehen, wie diese Algorithmen funktionieren, aber ich konnte keine einfache Erklärung finden. Ich würde es sehr schätzen, wenn mir jemand eine Beschreibung dieser Algorithmen liefern oder auf sie hinweisen könnte, die leichter zu verstehen ist als die Beschreibung in den Originalpapieren. Vielen Dank.

Answer 1

Zuallererst lassen Sie mich Ihnen die Links zu den Papieren, über die Sie sprachen, zur Verfügung stellen.

Eppstein Papier: D. Eppstein, “Finding the k shortest paths,” SIAM J. Comput., vol. 28, no. 2, pp.652–673, Feb. 1999

Yen Papier: J. Y. Yen, “Finding the K Shortest Loopless Paths in a Network,” Management Science, vol. 17, no. 11, pp. 712–716, 1971.

Hier ist meine Erklärung des Algorithmus Yen:

Yen-Algorithmus verwendet zwei Listen, dh Liste A (permanent kürzeste Wege von der Quelle zum Ziel - chronologisch geordnet) und Liste B (vorläufige/mögliche kürzeste Wege). Zuerst müssen Sie den kürzesten Weg von der Quelle zum Ziel finden, indem Sie einen geeigneten Algorithmus für den kürzesten Weg verwenden (z.B. Dijkstra). Dann nutzt Yen die Idee, dass die k-ten kürzesten Pfade Kanten und Unterpfade (Pfad von der Quelle zu irgendwelchen Zwischenknoten innerhalb der Route) von (k-1) -ten kürzesten Pfad teilen können. Dann müssen Sie den (k-1) -ten kürzesten Weg nehmen und jeden Knoten in der Route der Reihe nach unerreichbar machen, d. H. Eine bestimmte Kante abfärben, die zu dem Knoten innerhalb der Route führt. Sobald der Knoten nicht erreichbar ist, suchen Sie den kürzesten Pfad vom vorhergehenden Knoten zum Ziel. Dann haben Sie eine neue Route, die durch Anhängen des gemeinsamen Subpfades (von der Quelle zum vorhergehenden Knoten des nicht erreichbaren Knotens) erstellt wird und den neuen kürzesten Pfad vom vorhergehenden Knoten zum Ziel hinzufügt. Diese Route wird dann zu der Liste B hinzugefügt, vorausgesetzt, dass sie nicht zuvor in der Liste A oder in der Liste B erschienen ist. Nachdem Sie dies für alle Knoten in der Route wiederholt haben, müssen Sie die kürzeste Route in Liste B finden und diese in die Liste A verschieben. Sie müssen diesen Vorgang nur für die Anzahl der Ks wiederholen, die Sie haben.

Dieser Algorithmus hat eine Rechenkomplexität von O (kn^3). Bitte lesen Sie das Papier für weitere Details.

Der Algorithmus ist wie folgt:

G = Adjacent Matrix of the Network 
Initialize: 
A_1 = shortest-path from source to destination 
Glocal ← Local copy of G 
for k = 2 → K do 
for i = 1 → [len(A_(k−1)) − 1] do 
    Current Node ← A_(k−1) [i] 
    Ri ← Sub-path (root) from source till current node in A_(k−1) 
    for j = 1 → k − 1 do 
    Rj ← Sub-path (root) from source till current node in A_j 
    if Ri == Rj then 
    Next Node ← Aj [i+1] 
    Glocal(Current Node, Next Node) ← infinity 
    Current Node ← unreachable 
    end if 
    end for 
    Si ← Shortest-path from current node till destination 
    Bi ← Ri + Si 
end for 
A_k ← Shortest-path amongst all paths in B 
Restore original graph: Glocal ← Local copy of G 
end for 

Leider habe ich nicht Eppstein ein verwendet als Yen-Algorithmus für mein Problem optimal war.

Hoffe, das hilft. Prost.

=====

Edit:

haben Sie einen Blick auf die auch wikipedia entry. Es hat ein schönes Beispiel.

=====

Edit:

ich einige Implementierungen in C gefunden Die Links sind wie folgt:

Eppstein implementation und Loading Graph for Eppstein. Wenn Sie interessiert sind, gibt es einen lazy version von Eppstein.Der Link lautet wie folgt:

Lazy Eppstein by Jimenez and Marzal

=====

Edit:

Just another link. Dieser enthält mehrere Implementierungen (C/C++).

=====

Edit:

ich ein good explanation von Eppstein-Algorithmus gefunden haben.