Considere el gráfico dirigido que se muestra en la siguiente figura. Hay varios caminos más cortos entre los vértices S y T. ¿Cuál será informado por el algoritmo de camino más corto de Dijkstra? Suponga que, en cualquier iteración, la ruta más corta a un vértice v se actualiza solo cuando se descubre una ruta estrictamente más corta a v.
(A) SDT
(B) SBDT
(C) SACDT
(D) SACET
Respuesta: (D)
Explicación: Consulte el algoritmo de ruta más corta de Dijkstra
Cuando el algoritmo alcanza el vértice ‘C’, los valores de distancia de ‘D’ y ‘E’ serían 7 y 6 respectivamente. Entonces, el próximo vértice elegido sería ‘E’
Quiz de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA