PUERTA | PUERTA CS 2008 | Pregunta 45

El algoritmo de ruta más corta de fuente única de Dijkstra cuando se ejecuta desde el vértice a en el siguiente gráfico, calcula la distancia de ruta más corta correcta para

(A) solo el vértice a
(B) solo los vértices a, e, f, g, h
(C) solo los vértices a, b, c, d
(D) todos los vértices

Respuesta: (D)
Explicación: el camino más corto de fuente única de Dijkstra no se garantiza que funcione para gráficos con bordes de peso negativos, pero funciona para el gráfico dado.
Dejanos ver…

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

Cuestionario de esta pregunta