Algorytmy i struktury danych · Senior · Pytanie 4 z 75
Jaka jest złożoność Floyda-Warshalla i kiedy jest rozsądnym wyborem?
- 1O(V log V); dla ścieżek z jednego źródła w ogromnych grafach
- ✓Poprawna odpowiedź: O(V³); dla najkrótszych ścieżek między wszystkimi parami w małych gęstych grafach
- 3O(E); do sprawdzania, czy graf jest spójny
Wyjaśnienie
To trzy zagnieżdżone pętle po wierzchołkach, aktualizujące dist[i][j] przez każdy pośredni k. Prosty i radzi sobie z ujemnymi krawędziami (bez ujemnych cykli), ale przy V = 10 000 to już 10¹² kroków.