Bi Directional Dijkstra
1.0.0
Bei einem Diagramm mit nicht negativen Kantengewichten, einem Quellscheitelpunkt und einem Zielvertef . Finden Sie den kürzesten Weg zwischen s und t
Aber warum verwenden wir nicht einfach Dijkstra's Algorithmus, um das Problem zu lösen?
0 (E + Vlogv) ist die schlimmste Fallkomplexität des Dijkstra -Algorithmus, der ziemlich schnell ist. Für eine Grafik mit 20 Millionen Eckpunkten und 50 Millionen Kanten funktioniert es jedoch durchschnittlich mehrere Sekunden. Wir brauchen also etwas deutlich schnelleres.
Bevor wir uns mit den Details der bidirektionalen Suche befassen, lassen Sie uns das Konzept von "sechs Grad der Trennung" untersuchen,
- 1929 schlug ein ungarischer Autor, Frigyes Karinthy, zum ersten Mal das Konzept von "sechs Grad der Trennung" in seinen Kurzgeschichtenketten vor.
- Sechs Grad Trennung ist die Idee, dass alle Lebewesen und alles andere auf der Welt sechs oder weniger Schritte voneinander entfernt sind.
Schauen wir uns nun das beliebteste soziale Netzwerk Facebook an. Angenommen, eine durchschnittliche Person auf Facebook hat rund 100 Freunde. Wenn wir dann Freunde von Freunden dieser Person betrachten, sind es 100*100, die 10.000 Freunde von Freunden sind. Wenn wir "Freunde von Freunden von Freunden" betrachten, wird das 100 -mal mehr oder 1 Millionen mehr sein. Und wenn wir das sechs Mal fortsetzen, werden wir 1 Billion Menschen haben.
Die Weltbevölkerung beträgt jedoch 7,6 Million.
Wie finden wir nun den kürzesten Weg zwischen zwei zufälligen Personen A und B über ihre Verbindungen im sozialen Netzwerk?
Betrachten wir die bidirektionale Suche. Wir werden also Freunde von Freunden von Freunden von A und Friends of Friends of Friends of Friends of B in Betracht ziehen, wenn das Konzept von sechs Abschlüssen der Trennung wahr ist, es wird eine gewöhnliche Person unter Freunden von Freunden von Freunden von A und Friends of Friends of Friends of B. geben, dann können wir leicht den kürzesten Weg finden, der A und B. verbindet und B.
Beachten Sie, dass wir ungefähr 1 Millionen Freunde von Freunden von Freunden für A und B haben werden. Insgesamt werden wir in diesem Fall nur 2 Millionen Menschen in Betracht ziehen.
Der Algorithmus des normalen Dijkstra müsste im sozialen Netzwerk ungefähr 2 Milliarden Menschen suchen, um den kürzesten Weg zwischen A und B. zu finden
Darin führen wir zwei gleichzeitige Suchanfragen durch: einen vorwärts aus dem Anfangszustand und einen rückwärts vom Ziel und stoppen, wenn sich die beiden in der Mitte treffen.
- BAU GR (umgekehrter Diagramm) bauen
- Starten Sie Dijkstra aus S (Quelle) in G und von T (Ziel) in GR
- Wechsel zwischen Dijkstra -Schritten in G und in GR
- Stoppen Sie, wenn ein Scheitelpunkt "V" sowohl in G als auch in GR verarbeitet wird.
- Berechnen Sie den kürzesten Weg zwischen S und T.
Berechnung des kürzesten Pfades zwischen S und T: Sei dist [u] die Entfernungsschätzung im Vorwärtsdijkstra aus S in G. Sei DURT [u] die Entfernungsschätzung in der rückständigen Dijkstra von T in gr. Nachdem ein Knoten "V" sowohl in G als auch in G. verarbeitet wurde, geht ein kürzester Weg von S zu t durch einen Knoten "u", der entweder in G, in gr oder in beiden und D (s, t) = dist [u] + dest [u] verarbeitet wird.
