¿Qué significa relaxation of an edge en el contexto de la teoría de grafos? Me encontré con esto mientras estudiaba el algoritmo de Dijkstra para el camino más corto de fuente única.Relajación de un borde en el algoritmo de Dijkstra
Here's una buena descripción del algoritmo que también explica la noción de relajación.
La noción de "relajación" proviene de una analogía entre la estimación de la ruta más corta y la longitud de un muelle de tensión helicoidal, que no está diseñado para la compresión. Inicialmente, el costo de la ruta más corta es una sobreestimación, como un resorte estirado. Como se encuentran caminos más cortos , el costo estimado se reduce, y el muelle es relajado. Eventualmente, se encuentra la ruta más corta, si existe, y el resorte se ha relajado a su longitud de reposo.
El proceso de relajación en el algoritmo de Dijkstra se refiere a la actualización del coste de todos los vértices conectados a un vértice v, si esos costes podrían mejorarse mediante la inclusión de la ruta de acceso a través de v.
Relaxing un borde, (un concepto también puede encontrar otros algoritmos de ruta más corta) está tratando de reducir el costo de llegar a un vértice utilizando otro vértice.
Está calculando las distancias desde un vértice inicial, por ejemplo S, a todos los demás vértices. En algún momento, tiene resultados intermedios: estimaciones actuales. La relajación es el proceso donde se verifica, para algunos vértices u y v:
if directly_connected(v, u)
if est(S, v) > est(S, u) + dist(u,v)
est(S, v) = est(S, u) + dist(u, v)
donde est(S,a) es la estimación actual de la distancia, y dist(a,b) es la distancia entre dos vértices que son vecinos en el grafico.
Lo que básicamente mirando en el proceso de relajación es resistente a su estimación actual de un a b podría mejorarse "desviar" el camino a través c (este "desvío" sería la longitud de una ruta desde a a c y desde c a b).