Kürzeste Entfernung nach Straßenzusatzabfragen I

Lösung:

Wir müssen das Hinzufügen von Straßen zwischen Städten simulieren und nach jeder hinzugefügten Straße den kürzesten Weg von Stadt 0 zu Stadt n - 1 berechnen. Angesichts der Einschränkungen und der Art des Problems können wir Breadth-First Search (BFS) für ungewichtete Diagramme verwenden.

Ansatz:

1. Grafikdarstellung:

   • Wir können die Städte und Straßen mithilfe einer Adjazenzliste darstellen. Zunächst hat jede Stadt i eine Straße zur Stadt i 1 für alle 0 <= i < n - 1.
   • Nach jeder Abfrage fügen wir die Straße von u_i nach v_i in das Diagramm ein.

2. Berechnung des kürzesten Pfades (BFS):

   • Wir können BFS verwenden, um den kürzesten Weg von Stadt 0 zu Stadt n - 1 zu berechnen. BFS funktioniert hier gut, da alle Straßen das gleiche Gewicht haben (jede Straße hat eine Länge von 1).

3. Iterieren über Abfragen:

   • Für jede Abfrage fügen wir die neue Straße zum Diagramm hinzu und verwenden dann BFS, um den kürzesten Weg von Stadt 0 zu Stadt n - 1 zu finden. Nach der Verarbeitung jeder Abfrage speichern wir das Ergebnis im Ausgabearray.

4. Effizienz:

   • Da wir BFS nach jeder Abfrage verwenden und die Diagrammgröße höchstens 500 Städte mit bis zu 500 Abfragen betragen kann, beträgt die Zeitkomplexität für jedes BFS O(n·m), wobei n die Anzahl der Städte und m ist die Anzahl der Straßen. Wir müssen BFS bis zu 500 Mal durchführen, damit die Lösung innerhalb der Problembeschränkungen effizient läuft.

Lassen Sie uns diese Lösung in PHP implementieren: 3243. Kürzeste Entfernung nach Straßenzusatzabfragen I

  
  
  Erläuterung:




Diagramminitialisierung:


Ein Adjazenzlistendiagramm wird zur Darstellung der Städte und Straßen verwendet.
Anfangs gab es Straßen nur zwischen aufeinanderfolgenden Städten (i bis i 1).



BFS-Funktion:


BFS wird verwendet, um die kürzeste Entfernung von Stadt 0 zu Stadt n - 1 zu berechnen. Wir unterhalten eine Warteschlange für BFS und ein Array-Abstände, um die Mindestanzahl von Straßen (Kanten) zu speichern, um jede Stadt zu erreichen.
Anfangs ist die Entfernung zur Stadt 0 auf 0 gesetzt, und alle anderen Städte haben eine Entfernung von unendlich (PHP_INT_MAX).
Während wir jede Stadt in der BFS-Warteschlange verarbeiten, aktualisieren wir die Entfernungen für ihre Nachbarstädte und fahren fort, bis alle erreichbaren Städte besucht sind.



Abfrageverarbeitung:


Bei jeder Abfrage wird die neue Straße zum Diagramm hinzugefügt (u -> v).
BFS wird aufgerufen, um nach der Aktualisierung den kürzesten Weg von Stadt 0 zu Stadt n-1 zu berechnen.
Das Ergebnis von BFS wird im Ergebnisarray gespeichert.



Ausgabe:

Das Ergebnisarray enthält die kürzesten Pfadlängen nach jeder Abfrage.



Zeitkomplexität:


Jedes BFS benötigt O(n·m), wobei n die Anzahl der Städte und m die Anzahl der Straßen ist. Da die Anzahl der Abfragen q beträgt, beträgt die Gesamtzeitkomplexität O(q * (n m)), was für die gegebenen Einschränkungen effizient sein sollte.





  
  
  Beispielhafte Vorgehensweise:


Für die Eingabe n = 5 und Abfragen = [[2, 4], [0, 2], [0, 4]]:


Zunächst sind die Straßen [0 -> 1 -> 2 -> 3 -> 4].
Nach der ersten Abfrage [2, 4] sind die Straßen [0 -> 1 -> 2 -> 3 -> 4] und der kürzeste Weg von 0 nach 4 ist 3 (unter Verwendung des Pfades 0 -> 1 -> 2 -> 4).
Nach der zweiten Abfrage [0, 2] sind die Straßen [0 -> 2, 1 -> 2 -> 3 -> 4] und der kürzeste Weg von 0 nach 4 ist 2 (unter Verwendung des Pfads 0 -> 2 -> 4).
Nach der dritten Abfrage [0, 4] sind die Straßen [0 -> 2, 1 -> 2 -> 3 -> 4], und der kürzeste Weg von 0 nach 4 ist 1 (direkte Straße 0 -> 4).


Die Ausgabe ist also [3, 2, 1].


  
  
  Abschließende Gedanken:



Die Lösung verwendet BFS für jede Abfrage, um den kürzesten Pfad effizient zu berechnen.
Das Diagramm wird dynamisch aktualisiert, wenn bei jeder Abfrage neue Straßen hinzugefügt werden.
Die Lösung funktioniert gut innerhalb der Problembeschränkungen und verarbeitet effizient bis zu 500 Anfragen mit bis zu 500 Städten.


Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonKürzeste Entfernung nach Straßenzusatzabfragen I. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!