Рубрики

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

Алгоритм Дейкстры с одним источником кратчайшего пути при запуске из вершины а в приведенном ниже графике вычисляет правильное расстояние кратчайшего пути до


(А) только вершина а
(B) только вершины a, e, f, g, h
(C) только вершины a, b, c, d
(D) все вершины

Ответ: (Д)
Пояснение: кратчайший путь Дейкстры с одним источником не гарантируется для графов с отрицательными весовыми ребрами, но он работает для данного графа.
Покажи нам…

Давайте запустим 1-й проход
б 1
b является минимальным, поэтому самое короткое расстояние до b равно 1.

После 1-го прохода расстояния
с 3, е -2.
е минимально, поэтому кратчайшее расстояние до е равно -2

После 2-го прохода расстояния
с 3, f 0.
f является минимальным, поэтому самое короткое расстояние до f равно 0

После 3-го прохода расстояния
с 3, г 3.
Оба одинаковы, давайте возьмем g. поэтому самое короткое расстояние до g составляет 3.

После 4-го прохода расстояния
с 3, ч 5
c является минимальным, поэтому самое короткое расстояние до c равно 3

После 5-го прохода расстояния
ч -2
h минимально, поэтому самое короткое расстояние до h равно -2
Тест на этот вопрос

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

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

0.00 (0%) 0 votes