Алгоритми та структури даних · Senior · Запитання 4 з 75
Яка складність Флойда-Воршелла і коли він доречний?
- 1O(V log V); для шляхів з однієї вершини на величезних графах
- ✓Правильна відповідь: O(V³); для найкоротших шляхів між усіма парами на малих щільних графах
- 3O(E); для перевірки, чи зв'язний граф
Пояснення
Це три вкладені цикли по вершинах, що оновлюють dist[i][j] через кожну проміжну k. Простий і працює з від'ємними ребрами (без від'ємних циклів), але при V = 10 000 це вже 10¹² кроків.