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. Danke.
Zunächst möchte ich Ihnen die Links zu den Papieren geben, über die Sie gesprochen haben.
Eppsteins Beitrag: D. Eppstein, "Finden der k kürzesten Wege", SIAM J. Comput., Vol. 28, nein. 2, pp.652-673, Feb. 1999
Hier ist meine Erklärung für Yens Algorithmus:
Der Yen-Algorithmus verwendet zwei Listen, d. h. Liste A (permanente kürzeste Wege von Quelle zu Ziel - chronologisch geordnet) und Liste B (vorläufige / in Frage kommende 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 rechnerische Komplexität von O (kn ^ 3). Bitte lesen Sie das Papier für weitere Details.
Der Algorithmus ist wie folgt:
%Vor%Leider habe ich Eppsteins nicht benutzt, da Yens Algorithmus für mein Problem optimal war.
Hoffe, das hilft. Prost.
=====
Bearbeiten:
Schauen Sie sich auch den Wikipedia-Eintrag an. Es hat ein schönes Beispiel.
=====
Bearbeiten:
Ich habe einige Implementierungen in C gefunden. Die Links sind wie folgt:
Eppstein-Implementierung und Lade Grafik für Eppstein .
Wenn Sie interessiert sind, gibt es eine faule Version von Eppstein. Der Link lautet wie folgt:
Lazy Eppstein von Jiménez und Marzal
=====
Bearbeiten:
Nur ein weiterer Link . Dieser enthält mehrere Implementierungen (C / C ++).
=====
Bearbeiten:
Ich habe eine gute Erklärung von Eppsteins Algorithmus gefunden.
Tags und Links algorithm graph-algorithm shortest-path