Was ist ein geeigneter BFS-artiger optimaler Pfadalgorithmus für mehrere Eingänge und mehrere Ausgänge?

Question

Ich suche nach einem optimalen Pfadalgorithmus, der den optimalen Pfad von einem der Startknoten zu den nächsten Ausgangsknoten findet.

Die Grafik in diesem Fall ist ein quadratisches Gitter und alle Kosten für ein Nachbarquadrat sind 1. Alle Optimierungen mit diesen Einschränkungen sind in Ordnung.

Grundsätzlich geben Sie das Quadrat Gitter von einem zufällig gewählten Eingang, jetzt möchten Sie den nächstgelegenen Pfad zu einem der gegebenen Ausgänge finden.

Bis jetzt mache ich BFS mehrmals, einmal für jeden Ausgang und kombiniere die Ergebnisse. Obwohl ich bezweifle, dass dies der performanteste Weg ist, dies zu tun.

Answer 1

Sie starten BFS an allen Ausgängen. Wenn Sie ein neues Quadrat entdecken, ist die Entfernung zum nächsten Ausgang die Entfernung des vorherigen Quadrats +1 und die Pfadrichtung zum vorherigen Quadrat.

Da keines der (Abstands-, Richtungs-) Tupel davon abhängt, wo Sie es eingeben, können Sie diese Werte für alle Quadrate einmal vorberechnen, so dass Sie die Suche nicht erneut durchführen müssen, wenn Sie an einem neuen Eingang beginnen.