El algoritmo de Floyd-Warshall para el cálculo de las rutas más cortas de todos los pares se basa en:
(A) Paradigma codicioso.
(B) Paradigma divide y vencerás.
(C) Paradigma de programación dinámica.
(D) ni codicioso ni divide y vencerás ni paradigma de programación dinámica.
Respuesta: (C)
Explicación: El algoritmo Floyd Warshall es un algoritmo basado en programación dinámica .
Encuentra todos los pares de rutas más cortas utilizando la siguiente naturaleza recursiva del problema.
Para cada par (i, j) de vértices de origen y destino respectivamente, hay dos casos posibles.
1) k no es un vértice intermedio en el camino más corto de i a j. Mantenemos el valor de dist[i][j] como está.
2) k es un vértice intermedio en el camino más corto de i a j. Actualizamos el valor de dist[i][j] como dist[i][k] + dist[k][j].
La siguiente figura está tomada del libro de Cormen. Muestra la propiedad de subestructura óptima anterior en el problema del camino más corto de todos los pares.
Dado que hay subproblemas superpuestos en la recursividad, utiliza programación dinámica.
Cuestionario 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