Сложность времени выполнения Флойда Уоршалла с точки зрения ребер

Question

Выразите время выполнения Θ() алгоритма Флойда-Варшалла для задачи кратчайшего пути всех пар для графа G(V, E): i. В терминах количества вершин V в G. ii. В терминах числа ребер E в плотном графе G. iii. В терминах числа ребер E в разреженном графе G.

для числа я. это будет O(V^3) . (поправьте меня если я ошибаюсь). для числа II и III. Я не мог найти способ сделать это. это все еще O(E^3) для обоих?

Answer 1

В стандартной реализации алгоритма Флойда-Варшалла есть три вложенных цикла, которые проходят по вершинам графа. Это дает сложность времени O(V^3), как вы сказали, и не зависит от размера E.

Если вы определяете плотный граф как тот, где E ~ V^2, и разреженный граф как тот, где E ~ V, то ваши ответы на (ii) и (iii) будут O(E^(3/2)) и O(E^3) соответственно.