dijkstra - ¿Por qué lo llamamos "relajante" una ventaja?
bellman-ford (2)
En el algoritmo del camino más corto de Dijkstra y otros, examinar un borde para ver si ofrece un mejor camino a un nodo se conoce como relajar el borde. ¿Por qué se llama relajante?
En general, matemáticamente, la relajación está haciendo un cambio que reduce las restricciones. Cuando el algoritmo de Dijkstra examina un borde, elimina un borde de la agrupación, reduciendo así el número de restricciones.
No es una terminología terriblemente útil, pero piensa en lo genial que sonarás al decirlo.
No creo que la pregunta esté relacionada con el concepto matemático del que se habla en la respuesta actual aceptada. Estoy basando mi respuesta en la segunda edición del libro de Cormen (CLRS), específicamente en el capítulo 24 en una sección sobre la relajación.
Contexto: está buscando la ruta más corta entre un nodo y todos los demás nodos. Imagina que tienes dos nodos u y v . Ya tienes un camino intermedio para ellos.
relax (u, v) es una función que debe leerse como "relax v utilizando u ". Prefiero entender la función como "acortar la distancia de v a s usando u ". Te estás preguntando si deberías renunciar a tu ruta actual sv en favor de transformarla en suv . Todo lo que tiene que hacer para ver si la distancia de su más el costo adicional de la flecha uv es mejor que la distancia sv . La imagen examina la función.
