Рубрики

ВОРОТА | GATE 2017 MOCK II | Вопрос 16

Рассмотрим следующие утверждения об алгоритме Беллмана Форда для нахождения кратчайшего пути в ориентированном связном графе G, имеющем интегральные веса ребер.

Утверждение I: Он всегда обнаружит отрицательный граничный весовой цикл в G, достижимый из источника.

Утверждение II: Это всегда даст правильный ответ для графа G.

Выберите один из вариантов, приведенных ниже.

(A) Оба утверждения верны
(Б) Оба утверждения являются ложными

(C) Заявление I верно, а Заявление II неверно
(D) Утверждение II верно, а Утверждение I неверно

Ответ: (C)
Объяснение: Утверждение 1 верно, как и в n-й итерации Беллмана Форда, если длина пути любого узла, достижимого из источника, уменьшается, это означает, что у нас есть отрицательный цикл веса графа на графике.

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

ВОРОТА | GATE 2017 MOCK II | Вопрос 16

0.00 (0%) 0 votes