Рубрики

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

Рассмотрим ориентированный граф, показанный на рисунке ниже. Существует несколько кратчайших путей между вершинами S и T. Какой из них будет сообщен алгоритмом кратчайшего пути Диджстры? Предположим, что на любой итерации кратчайший путь к вершине v обновляется только при обнаружении строго более короткого пути к v.


(А) SDT
(B) SBDT
(С) SACDT
(D) SACET

Ответ: (Д)
Объяснение: См . Алгоритм кратчайшего пути Дейкстры.

Когда алгоритм достигает вершины «C», значения расстояний «D» и «E» будут соответственно 7 и 6. Таким образом, следующая выбранная вершина будет 'E'
Тест на этот вопрос

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

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

0.00 (0%) 0 votes