Сложность времени выполнения Floyd Warshall с точки зрения ребер

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

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


graph time-complexity floyd-warshall
person Alviss Min    schedule 14.09.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person Globe Theatre    schedule 14.09.2017