Рубрики

ВОРОТА | GATE-CS-2009 | Вопрос 12

Какое из следующих утверждений является верным в отношении алгоритма Беллмана-Форда по кратчайшему пути?

P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable 
   from the source. 

(A) P Только
(B) Q Только
(C) и P и Q
(D) Ни P, ни Q

Ответ: (Б)
Объяснение: Алгоритм кратчайшего пути Беллмана-Форда является алгоритмом кратчайшего пути из одного источника. Таким образом, он может найти только циклы, которые достижимы из данного источника, а не любой отрицательный цикл веса. Рассмотрим отключение, когда отрицательный весовой цикл вообще недоступен для источника.

Если существует отрицательный весовой цикл, то он будет отображаться по кратчайшему пути, поскольку отрицательный весовой цикл всегда будет образовывать более короткий путь при повторении цикла снова и снова.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2009 | Вопрос 12

0.00 (0%) 0 votes