Ich habe einen Graphen G mit einem Startknoten S und einem Endknoten E. Das Besondere an diesem Graphen ist, dass anstelle von Kanten Kosten anfallen, hier sind es die Knoten, die Kosten haben. Ich möchte den Weg (eine Menge von Knoten, W) zwischen S und E finden, so dass max (W) minimiert wird. (In Wirklichkeit bin ich nicht an W interessiert, nur max (W)) Äquivalent, wenn ich alle Knoten mit Kosten größer als k entfernen, was ist das kleinste k, so dass S und E noch verbunden sind?
Ich habe eine Idee, möchte aber wissen, ob sie richtig und optimal ist. Hier ist mein aktueller Pseudocode:
%Vor%Ich glaube, es ist der schlimmste Fall O (n log n), wobei n die Anzahl der Knoten ist.
Hier sind einige Details für mein spezifisches Problem (Perkolation), aber ich bin auch an Algorithmen für dieses Problem im Allgemeinen interessiert. Die Knotengewichte sind zufällig zwischen 0 und einem gegebenen Maximalwert verteilt. Meine Knoten sind auf der R²-Ebene verteilt, und eine Kante zwischen zwei Knoten existiert, wenn die Entfernung zwischen zwei Knoten kleiner als eine gegebene Konstante ist. Es gibt potentiell sehr viele Knoten, so dass sie on-the-fly generiert werden (versteckt im foreach im Pseudocode). Mein Startknoten ist in (0,0) und der Endknoten ist ein beliebiger Knoten in einer Entfernung größer als R von (0,0).
EDIT: Die Gewichte auf den Knoten sind Gleitkommazahlen.
Ausgehend von einem leeren Graphen können Sie Scheitelpunkte (und ihre Kanten zu bestehenden Nachbarn) nacheinander in wachsender Reihenfolge einfügen, indem Sie ein schnelle Vereinigung / Datenstruktur finden , um die Menge der verbundenen Komponenten zu erhalten. Dies ist genau wie der Kruskal-Algorithmus , um minimale Spannbäume zu erstellen, aber anstatt Kanten nacheinander hinzuzufügen, z Für jeden Vertex v, den Sie verarbeiten, würden Sie die Komponenten von all von vs Nachbarn kombinieren.
Sie verfolgen auch, welche zwei Komponenten die Anfangs- und Endscheitelpunkte enthalten. (Anfangs comp (S) = S und comp (E) = E; vor jeder Vereinigungsoperation können die zwei Eingangskomponenten X und Y geprüft werden, um zu sehen, ob entweder comp (S) oder comp (E) ist, und der Letzteres wird in O (1) -Zeit entsprechend aktualisiert.) Sobald diese beiden Komponenten zu einer einzigen Komponente werden (dh comp (S) = comp (E)), hören Sie auf. Der soeben hinzugefügte Knoten ist der maximale Gewichtsvertex auf dem Pfad zwischen S und E, der das maximale Gewicht eines Eckpunkts minimiert.
[BEARBEITEN: Informationen zur Komplexität der Zeit hinzugefügt]
Wenn der Graph n Knoten und m Kanten enthält, dauert es 0 (n log n) Zeit, um die Knoten nach Gewicht zu sortieren. Es wird höchstens m Union-Operationen geben (da jede Kante verwendet werden könnte, um zwei Komponenten zu kombinieren). Wenn eine einfache disjunkte Mengen-Datenstruktur verwendet wird, könnten alle diese Vereinigungsoperationen in der Zeit O (m + n log n) durchgeführt werden, und dies würde die gesamte Zeitkomplexität werden; Wenn auch die Pfadkomprimierung verwendet wird, fällt diese auf O (m A (n)), wobei A (n) die unglaublich langsam wachsende inverse Ackermann-Funktion ist, aber die gesamte Zeitkomplexität bleibt unverändert, da die anfängliche Sortierung dominiert.
Unter Annahme von ganzzahligen Gewichten wird Pham Trungs Ansatz für die binäre Suche die Zeit O ((n + m) log maxW) annehmen, wobei maxW der schwerste Eckpunkt im Graphen ist. Auf spärlichen Graphen (wo m = O (n)), wird dies zu O (n log maxW), während meins zu O (n log n) wird, also wird sein Algorithmus meinen schlagen, wenn log (maxW) & lt; & lt; log (n) (d. h. wenn alle Gewichte sehr klein sind). Wenn sein Algorithmus in einem Graphen mit großen Gewichten aufgerufen wird, aber nur eine kleine Anzahl von distinct -Wichtungen, dann wäre eine mögliche Optimierung, die Gewichte in O (n log n) -Zeit zu sortieren und dann alle zu ersetzen mit ihren Rängen in der sortierten Reihenfolge.
Dieses Problem kann mit binäre Suche gelöst werden.
Nehmen Sie an, dass die Lösung x ist. Von Anfang an werden wir BFS oder DFS verwenden, um das Diagramm zu ermitteln, und nur die Knoten mit dem Gewicht & lt; = x aufrufen. Wenn also Start und Ende verbunden sind, kann x die Lösung sein. Wir können den optimalen Wert für x finden, indem wir die binäre Suche anwenden.
Pseudocode
%Vor%Hinweis : Wir müssen nur die Gewichtungen anwenden, die im Graphen vorhanden sind. Dies kann helfen, die Zeitkomplexität der binären Suche auf O (log n) zu reduzieren, wobei n die Anzahl der unterschiedlichen Gewichtungen ist
Wenn die Gewichtungen float sind, verwenden Sie einfach den folgenden Ansatz:
%Vor%Tags und Links algorithm graph-algorithm graph path-finding