Algoritmos | Graficar las rutas más cortas | Pregunta 3

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…

Ejecutemos el primer paso
b 1
b es mínimo, por lo que la distancia más corta a b es 1.

Después del 1er paso, las distancias son
c 3, e -2.
e es mínimo, por lo que la distancia más corta a e es -2

Después del segundo paso, las distancias son
c 3, f 0.
f es mínima, por lo que la distancia más corta a f es 0

Después del tercer paso, las distancias son
c 3, g 3.
Ambas son iguales, tomemos g. entonces la distancia más corta a g es 3.

Después del cuarto paso, las distancias son
c 3, h 5
c es el mínimo, por lo que la distancia más corta a c es 3

Después del quinto paso, las distancias son
h -2
h es el mínimo, por lo que la distancia más corta hasta h es -2
Cuestionario de esta pregunta