Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 3

Рассмотрим взвешенный неориентированный граф с положительными весами ребер, и пусть uv будет ребром в графе. Известно, что кратчайший путь от исходной вершины s до u имеет вес 53, а кратчайший путь от s до v имеет вес 65. Какое из следующих утверждений всегда верно?
(A) вес (U, V) (B) вес (U, V) ≤ 12
(С) вес (и, v)> 12
(D) вес (U, V) ≥ 12

Ответ: (D)
Объяснение:

Минимальный вес происходит, когда (S, U) + (U, V) = (S, V)

Остальное (S, U) + (U, V)> = (S, V)

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

ВОРОТА | Gate IT 2007 | Вопрос 3

0.00 (0%) 0 votes