Ich suche nach einer Möglichkeit, die BFS-Methode zu verbessern, mit der die kürzesten Pfade aus einer Quelle in einem ungewichteten gerichteten Graphen gefunden werden können, und das obige Problem in O (N + M) -Zeit zu lösen. N ist die Anzahl der Ecken, M ist die Anzahl der Kanten
Ich habe folgendes gedacht:
Verrechnen Sie die Scheitelpunkte des Graphen mit einer Kantenstärke zwischen ihnen. Aber das wäre definitiv falsch, denn dann würde ich die Eigenschaften des Graphen ändern und Ecken, die ursprünglich keine hatten, neue Kanten hinzufügen.
Ändern Sie die Kantengewichte auf 1 und 2. Und erstellen Sie dann Dummy-Scheitelpunkte in den Pfaden der Länge 2, um diese Kanten in Kanten mit der Gewichtung 1 zu konvertieren. Dies würde jedoch die falsche Antwort liefern.
In allgemeinerer Form: Wie kann ich in einem gerichteten Graphen die kürzesten Pfade aus einer Quelle finden, wenn die Kantengewichte in linearer Zeit zwischen 0 und MAX liegen? (MAX ist das maximale Kantengewicht)
Sie können bfs mit einigen Modifikationen verwenden: Pflegen Sie eine Deque statt einer Queue und fügen Sie einen Eckpunkt an der Vorderseite der Deque hinzu, wenn die 0-Kante verwendet wird, und sonst die Rückseite der Deque (ich meine jetzt 0-1) )
Ich denke, Sie können dies mit der Vertex-Kontraktion herausfinden. Nur ein Hinweis hier:
Bilden Sie zuerst verbundene Komponenten von Scheitelpunkten, die durch 0-gewichtete Kanten verbunden sind, und wählen Sie in jeder Komponente ein repräsentatives Element aus. Dies gibt Ihnen eine kontrahierte Grafik.
Lösen Sie dann das ungewichtete Problem.
Der wahre Pfad wird gebildet aus "Zwischenkanten" (Gewicht 1), die die repräsentativen Elemente verbinden, und "Innenkanten", die Eckpunkte innerhalb der Komponente von der ankommenden Zwischenkante zur abgehenden Zwischenkante verbinden. Mit anderen Worten, Sie müssen in der Lage sein, den Weg von einem Vertreter zu einem anderen Vertreter zu finden.
Es tut mir leid, aber in dieser Komplexität sollte dies nicht möglich sein.
Sie können dieses Tabellaries für die Komplexität von Algorithmen für den kürzesten Pfad
ansehenWenn Sie das Problem erklären, möchten Sie die Gewichte von 0 und 1 beibehalten. Wenn Sie es sich leisten können, die 0 Gewichtskanten zu entfernen, degeneriert dies zu einem kürzesten Pfad mit ungewichteten Rändern, der mit Ihrer gewünschten Komplexität solven sollte Suche wäre dann das Schlüsselwort)
Tags und Links algorithm graph shortest-path