Wie finde ich den kürzesten Weg von einem Scheitelpunkt in Menge zu Menge

7

Wenn ich einen Graphen , eine Teilmenge der Eckpunkte und eine zweite Menge von Eckpunkten , was ist der beste Weg, um den kürzesten Weg zu finden, der die verbindet zwei Sets? Das heißt, wir suchen einen kürzesten Weg unter allen - Wegen. Wir können auch davon ausgehen, dass alle Kantengewichte positiv sind.G=(V,E)SVS(VS)SS

So bin ich bisher mit diesem Problem umgegangen:

Ich habe bereits die Distanzmatrixinformationen für Graph die durch Anwenden des Floyd-Warshall-Algorithmus in einer früheren Operation berechnet wurden .(d)G

Ich iteriere dann über alle Eckpunkte in für jeden Eckpunkt in und finde das Paar mit dem kleinsten Wert in Matrix .SS(s1,s2)d

Der Dijkstra-Algorithmus wird dann verwendet, um den kürzesten Weg zwischen und zu berechnen , so dass die Verbindungsscheitelpunktsätze und .s1s2SS

Gibt es einen effizienteren Weg, um dasselbe Ergebnis zu erzielen?

guskenny83
quelle

Antworten:

6

Wenn alle Kantenlängen nicht negativ sind, kann dies in Zeit mit einem einzigen Aufruf des Dijkstra-Algorithmus gelöst werden.O(|E|lg|V|)

Wir werden die Grafik etwas ändern , indem Sie einen neuen Vertex Zugabe . Fügen Sie außerdem jedem Scheitelpunkt in eine Kante der Länge 0 von .ssS

Führen Sie als Nächstes den Dijkstra-Algorithmus ausgehend vom Quellscheitelpunkt . Dijkstra-Algorithmus berechnen Sie den Abstand von zu jedem anderen Eckpunkt , das heißt, es wird berechnet für alle . Beachten Sie, dass genau die Länge des kürzesten Pfades von einem Scheitelpunkt in zum Scheitelpunkt .ssvd(s,v)vVd(s,v)Sv

Berechnen Sie schließlich . Dies ist die Länge des kürzesten Weges von einem Scheitelpunkt in zu einem Scheitelpunkt in . Das ist deine Antwort.min{d(s,v):vS}SS

Floyd-Warshall muss nicht ausgeführt werden.

Wenn Sie negative Flanken haben können, kann dies in Zeit erfolgen. Ersetzen Sie einfach den Dijkstra-Algorithmus durch den Bellman-Ford-Algorithmus.O(|V||E|)

DW
quelle
1
Sie können sogar die Berechnung des Minimums speichern, indem Sie einen weiteren neuen Scheitelpunkt für hinzufügen . (Man sollte beachten, dass die Laufzeitgrenze annimmt , was vernünftig ist; kann wahrscheinlich hier als verbunden angenommen werden.)S|E|Ω(|V|)G
Raphael
danke für deine antwort, das macht sehr viel sinn. In Bezug auf Ihren Punkt, Floyd-Warshall nicht ausführen zu müssen, wäre es schneller, eine Suche im Entfernungsdiagramm durchzuführen, wenn ich Floyd-Warshall bereits für etwas anderes ausgeführt habe und diese Informationen bereits verfügbar habe? oder nicht? Da wir ohnehin dijkstra ausführen müssen, ist es nur schneller, die Dummy-Vertex-Methode zu verwenden?
Guskenny83
1
@ guskenny83, es kommt darauf an. Wenn Sie Floyd-Warshall bereits ausführen, dauert es , bis alle -Einträge in der Matrix nach gesucht sind, um den kürzesten Pfad mithilfe seiner Ausgabe zu finden . Dies kann langsamer oder schneller sein als das Ausführen des Dijkstra-Algorithmus, abhängig von der Größe der Mengen und des Graphen. Für spärliche Graphen und große Mengen ist es im schlimmsten Fall langsamer. O(|S||S|)d[u,v]uS,vSS,SS,S
DW