Gibt es irgendeine Implementierung von bidirektionalen Suche für den Dijkstra-Algorithmus?

Ich bin auf der Suche nach einer Implementierung bidirektionaler Suche (ein.k.a. "in der Mitte treffen" - Algorithmus) für Dijkstra (oder einer anderen Quelle-zu-Ziel-shortest-path-Algorithmus) in Java.

Als bidirektionale Suche die Bearbeitung ist schwieriger, als es aussieht (Graph-Algorithmen, p.26), will ich prüfen, eine vorhandene Implementierung, bevor das Rad neu erfinden!

P. S.: ich spreche bidirektionale Suche, nicht zu verwechseln mit einem bidirektionalen Graphen)

Hier ist ein Beispiel für eine knifflige Grafik:

Gibt es irgendeine Implementierung von bidirektionalen Suche für den Dijkstra-Algorithmus?

  • Meine Implementierung für die bidirektionale graph ist genau das gleiche wie im gerichteten Fall - ich füge einfach zwei Schneidkanten statt einer. Ich weiß nicht warum, glaubst du, ist es schwieriger.
  • Bidirektionaler dijkstra bedeutet, dass dijkstra ist die parallele Verarbeitung sowohl von Quelle und Ziel, die Komplexität zu reduzieren Kosten. Siehe en.wikipedia.org/w/index.php?title=Bidirectional_search
  • Ich bin nicht zu sehen, wie dieser Algorithmus ist wesentlich schwerer als ein normaler Dijkstra-Implementierung. (In jedem Fall, Implementierungen wird sehr unterschiedlich sein, je nachdem, wie der graph zur Verfügung gestellt, so dass jede Umsetzung, jemand anderes wird wahrscheinlich verlangen, umschreiben, sowieso.)
  • ah, sorry, ich konnte nicht öffnen Sie die ersten Artikel. Ich kenne dieses Konzept unter dem Namen "treffen in der Mitte". Es ist ein bisschen schwieriger dann die ursprünglichen Dijkstra-aber nicht viel. Vielleicht erwähnen Sie die Teile, die schwer für Sie?
  • Ich denke, es kann unklar sein, Wann Sie aufhören zu suchen, denn wenn wir aufhören, sofort nach der Sitzung, es wird nicht garantiert, dass der Pfad der kürzeste ist. Und stoppen, zu spät Ergebnisse in einem langsamen Algorithmus.
  • Hier ist eine Implementierung, aber es ist in C#, nicht in Java, und es scheint, dass der resultierende Pfad ist nicht immer optimal.
  • ein bisschen spät ... aber einen Blick in die github.com/graphhopper/graphhopper
  • es genagelt. Die Stopp-Bedingung ist nicht sofort offensichtlich, aber es ist einer. Siehe cs.princeton.edu/courses/archive/spr06/cos423/Handouts/...
  • Mögliche Duplikate von "Bidirektionale Dijkstra" von NetworkX

InformationsquelleAutor Fabien | 2012-05-28
  1. 6

    Ja, es ist zumindest in Java: https://github.com/coderodde/GraphSearchPal/blob/master/src/main/java/net/coderodde/gsp/model/support/BidirectionalDijkstraPathFinder.java

    In einer bidirektionalen Dijkstra-Algorithmus, pflegen Sie eigentlich zwei "Dijkstra-algorithmen": der Suchlauf vorwärts und rückwärts suchen. Nun, die vorwärts-Suche ähnelt, eine Menge, die einseitig Dijkstra-Algorithmus. Die rückwärts-Suche, jedoch, verläuft in "umgekehrter" Weise. Wenn es eine gerichtete Kante (umgangssprachlich genannt, ein arc) (u, v), die nach vorne suchen würde, durchqueren es von u zu v, in der Erwägung, dass die rückwärts-Suche würde das gleiche tun, in die entgegengesetzte Richtung.

    Weil die beiden such-Prozesse erfüllen (in der Regel), die irgendwo zwischen dem Quellknoten und dem Zielknoten, brauchen wir noch eine Abbruchbedingung, die in bidirektionalen Dijkstra-Algorithmus ist 

    g(top(OPEN_forward)) + g(top(OPEN_backward)) > l

    wo l ist die Länge des kürzesten bisher bekannten Pfad zwischen dem Quell-und Ziel-Knoten.

    Zusätzlichen code, den Sie sehen könnte, nur in bidirektionaler Ausführung ist die überprüfung der Möglichkeit der Verkürzung einen kürzesten Pfad Kandidaten jeder Zeit, die Sie verbessern die g Wert eines Knotens. (Die g Wert eines Knotens u ist die kürzeste (bisher bekannten) Entfernung der Knoten von dem aus die Suche gestartet, um u.)

    • Gibt es irgendeine chance, das schreiben in LaTeX SO?
    • Nein, es ist nicht aktiv (nicht so wie in CodeReview...) leider.
    InformationsquelleAutor coderodde
Schreibe einen Kommentar