En el algoritmo de camino más corto de Dijkstra y otros, examinar un borde para ver si ofrece una mejor ruta a un nodo se denomina relajar el borde. ¿Por qué se llama relajante?¿Por qué lo llamamos "Relajante" una ventaja?
En general, matemáticamente, relajación está haciendo un cambio que reduce las restricciones. Cuando el algoritmo de Dijkstra examina un borde, elimina un borde del grupo, lo que reduce el número de restricciones.
No es una terminología terriblemente útil, pero piensa en lo genial que sonarás al decirlo.
¿Podría aclarar cómo se pueden ver los bordes de la agrupación como restricciones? –
Piense en un vértice con muchos bordes que entran en él. Cuando comienzas, sabes que la solución debe incluir el peso del primer borde, el segundo borde, y así sucesivamente. En efecto, para los bordes a, b, c, d y e, comienzas diciendo "la ruta más corta debe incluir a, b, c, d, e". Luego eliminas e, y ahora sabes que debe incluir solo "a, b, c, d". Cada paso es * relajación * porque en cada paso elimina una condición que impone la solución actual. –
Supongo que no está 'entrando', sino 'dejándolo'? –