Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 45

GATE

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

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

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

Let us run the 1st pass
b 1
b is minimum, so shortest distance to b is 1.

After 1st  pass, distances are
c 3, e -2.  
e is minimum, so shortest distance to e is -2

After 2nd pass, distances are
c 3, f 0.  
f is minimum, so shortest distance to f is 0

After 3rd pass, distances are
c 3, g 3.  
Both are same, let us take g. so shortest distance to g is 3.

After 4th pass, distances are
c 3, h 5  
c is minimum, so shortest distance to c is 3

After 5th pass, distances are
h  -2
h is minimum, so shortest distance to h is -2

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

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

ВОРОТА | GATE CS 2008 | Вопрос 45

0.00 (0%) 0 votes