Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 38

Пусть G (V, E) неориентированный граф с положительными весами ребер. Алгоритм кратчайшего пути Дейкстры с одним источником может быть реализован с использованием структуры данных двоичной кучи с временной сложностью:
(A) O (| V | 2)
(B) O (| E | + | V | log | V |)
(C) O (| V | log | V |)
(D) O ((| E | + | V |) log | V |)

Ответ: (D)
Объяснение: см. Раздел «Сложность времени» http://espressocode.top/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 38

0.00 (0%) 0 votes