algorithm - historia - Relajación de una ventaja en el algoritmo de Dijkstra

dijkstra algorithm

Question

¿Qué significa la relaxation of an edge en el contexto de la teoría de grafos? Encontré esto mientras estudiaba el algoritmo de Dijkstra para la ruta más corta de una sola fuente.

Answer 1

El proceso de relajación en el algoritmo de Dijkstra se refiere a actualizar el costo de todos los vértices conectados a un vértice v, si esos costos se mejorarían al incluir la ruta a través de v.

Answer 2

Relajar un borde (un concepto que también puede encontrar en 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, digamos S , a todos los otros vértices. En algún momento, usted tiene resultados intermedios - estimaciones actuales. La relajación es el proceso donde se comprueban, 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 la gráfica.

Básicamente, lo que está verificando en el proceso de relajación es si su estimación actual de a a b podría mejorarse "desviando" el camino a través de c (este "desvío" sería la longitud de un camino de a a c y de c a b ).

Answer 3

supongamos en el gráfico si tenemos (u, v) ∈ E donde w (u, v) = 10 luego si agregando un tercer vértice entre ellos como w (u, y) = 1 yw (y, v) = 3 ahora encontramos un camino entre u y v con peso 1 + 3 = 4 <10. Ahora consideraremos el segundo camino como el más corto que es (u, y, v) e ignoraremos el primero, esto es relajación.

Answer 4

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 trayectoria más corta y la longitud de un resorte de tensión helicoidal, que no está diseñado para la compresión. Inicialmente, el costo del camino más corto es una sobrestimación, comparado con un resorte extendido. A medida que se encuentran caminos más cortos, el costo estimado se reduce y la primavera se relaja. Eventualmente, el camino más corto, si existe, se encuentra y el resorte se ha relajado a su longitud de descanso.