Рубрики

Алгоритмы | График кратчайших путей | Вопрос 8

В взвешенном графике предположим, что кратчайший путь от источника 's' к месту назначения 't' правильно рассчитан с использованием алгоритма кратчайшего пути. Верно ли следующее утверждение?
Если мы увеличим вес каждого ребра на 1, кратчайший путь всегда останется прежним.
(А) да
(Б) Нет

Ответ: (Б)
Объяснение: см. Следующий контрпример.

Имеется 4 ребра sa, ab, bt и st уйтов 1, 1, 1 и 4 соответственно. Кратчайший путь от s до t — это sa, ab, bt. Если мы увеличим вес каждого ребра на 1, кратчайший путь изменится на ст.


   1      1     1
s-----a-----b-----t
 \              /
   \          /
     \______/
        4

Тест на этот вопрос

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

Алгоритмы | График кратчайших путей | Вопрос 8

0.00 (0%) 0 votes