floyd warshall Laufzeit Komplexität in Bezug auf Kanten

Question

Drücken Sie die Laufzeit Θ() des Floyd-Warshall-Algorithmus für die alle Paare kürzester Weg Problem für einen Graphen G (V, E): i. In Bezug auf die Anzahl der Knoten V in G. ii. In Bezug auf die Anzahl der Kanten E in einem dichten Graphen G. iii. In Bezug auf die Anzahl der Kanten E in einem dünnen Graphen G.

für die Nummer i. es wäre O (V^3). (korrigiere mich wenn ich falsch liege). für Nummer ii und iii. Ich konnte keinen Weg finden, es zu tun. ist es immer noch O (E^3) für beide?

Answer 1

In der Standardimplementierung des Floyd-Warshall-Algorithmus gibt es drei verschachtelte Schleifen, die durch die Scheitelpunkte des Graphen verlaufen. Dies ergibt eine Zeitkomplexität von O (V^3) wie Sie sagten und ist unabhängig von der Größe von E.

Wenn Sie einen dichten Graphen definieren, in dem E ~ V^2 und ein dünner Graph sein sollen wo E ~ V, dann sind deine Antworten auf (ii) und (iii) O (E^(3/2)) bzw. O (E^3).