Pruebe una modificación del algoritmo Bellman – Ford. Este algoritmo mantiene un estado de programación dinámica dp(max_edges, curr_node) donde dp indica el costo mínimo para llegar de curr_node al nodo de destino utilizando como máximo max_edges .
Hay dos posibilidades aquí:
- La ruta óptima utiliza
max_edges - 1bordes. Si este es el caso,dp(max_edges, curr_node) = dp(max_edges - 1, curr_node) - La ruta óptima usa un borde saliente desde
curr_nodea otro nodo, luego usamax_edges - 1para llegar desde ese nodo al objetivo. Probamos esto para todos los bordes salientes decurr_node. Por lo tanto,dp(max_edges, curr_node) = min(for all nodes w such that there is an edge curr_node --> w (dp(max_edges - 1, w) + weight(curr_node, w)))
La respuesta final para nuestra recurrencia dp(max_edges, curr_node) será el mínimo de las condiciones anteriores.
- ¿Cuál es una manera simple de implementar la paginación en una matriz en Javascript?
- ¿Cuál es la clave para diferenciar y comparar dos algoritmos de aprendizaje automático?
- ¿Es 'Cracking the Coding Interview' una lectura obligatoria cuando se postula para ser un ingeniero front-end?
- ¿Alguien puede aprender las ideas asociadas con los algoritmos sin aprender a codificar primero?
- ¿Cómo se implementan las estructuras matemáticas básicas como +, -, *, / en los lenguajes de programación?
Ahora con los bordes e en una ruta simple, tenemos exactamente e + 1 nodos.
