Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 19

Какова временная сложность алгоритма кратчайшего пути Беллмана-Форда из одного источника на полном графе из n вершин?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Пояснение: Временная сложность алгоритма Беллмана-Форда составляет O (VE), где V — количество вершин, а E — количество ребер. Для полного графа с n вершинами V = n, E = O (n ^ 2). Таким образом, общая сложность времени становится O (n ^ 3)
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2013 | Вопрос 19

0.00 (0%) 0 votes