Ich las Einführung in Algorithmen 3rd Edition. Es gibt 3 Methoden, um das Problem zu lösen. Meine Anfrage betrifft zwei von ihnen.Dijkstra-Algorithmus vs entspannende Kanten in topologisch sortierten Graphen für DAG
Der eine ohne Namen
Der Algorithmus von topologisch startet die dag Sortierung (siehe Abschnitt 22.4) eine lineare Ordnung auf den Eckpunkten zu verhängen. Wenn dag einen Pfad vom Knoten u zum Knoten v enthält, dann geht v in der topologischen Sortierung v voraus. Wir machen nur einen Durchlauf über die Ecken in der topologisch sortierten Reihenfolge. Während wir jeden Eckpunkt bearbeiten, entspannen wir jede Kante, die den Eckpunkt verlässt.
Dijkstra-Algorithmus
Dies ist recht gut
bekanntWas das Buch zeigt, Zeitkomplexität ohne Namen ist O (V + E), sondern von Dijstra des O (ElogV). Wir können Dijkstra's nicht auf negatives Gewicht anwenden, aber wir können das andere verwenden. Was sind die Vorteile des Dijkstra-Algorithmus, außer dass er in zyklischen verwendet werden kann?
@NursultanZarlyk. Aus dem Buch: ** Die Laufzeit dieses Algorithmus ist einfach zu analysieren. Wie in Abschnitt 22.4 gezeigt, benötigt die topologische Sortierung der Zeile 1 die Zeit O (V + E). Der Aufruf von INITIALIZESINGLE-SOURCE in Zeile 2 dauert O (V) -Zeit. Die for-Schleife der Zeilen 3-5 macht eine Iteration pro Vertex. Insgesamt entspannt die for-Schleife der Zeilen 4-5 jede Kante genau einmal. (Wir haben hier eine Aggregatanalyse verwendet.) Da jede Iteration der inneren for-Schleife eine O (1) -Zeit benötigt, ist die Gesamtlaufzeit 0 (V + E), was linear in der Größe einer Adjazenzlisten-Repräsentation ist der Grafik. ** –
Beide richtig. Wenn der Graph ein dag ist, bei dem jeder Vorgänger mit allen seinen Nachfolgern verbunden ist, dann entspannt der erste Eckpunkt V-1 Kanten, der zweite wird V-2 Kanten usw. bis zum letzten Eckpunkt lockern. In dieser Art von Graphen kann dann E ~ V^2, also O (V^2 + E) = 0 (V + E) = 0 (V^2) –