Algorithmen und Datenstrukturen · Senior · Frage 4 von 75
Welche Komplexität hat Floyd-Warshall, und wann ist er eine vernünftige Wahl?
- 1O(V log V); für Wege von einer Quelle in riesigen Graphen
- 2O(V³); für kürzeste Wege zwischen allen Paaren in kleinen, dichten Graphen
- 3O(E); um zu prüfen, ob ein Graph zusammenhängend ist
Antwort zeigen
Richtige Antwort: O(V³); für kürzeste Wege zwischen allen Paaren in kleinen, dichten Graphen
Erklärung
Es sind drei verschachtelte Schleifen über Knoten, die dist[i][j] über jeden Zwischenknoten k aktualisieren. Einfach und mit negativen Kanten (ohne negative Zyklen) nutzbar, aber bei V = 10.000 sind es schon 10¹² Schritte.