¿Cuál es la condición de relajación en la teoría de grafos?

Question

Estoy tratando de comprender los conceptos principales de la teoría de grafos y los algoritmos dentro de ella. La mayoría de los algoritmos parecen contener una "Condición de relajación". No estoy seguro de qué es esto.

¿Podría alguien explicarlo por favor?

Un ejemplo de esto es el algoritmo de dijkstras, aquí está el pseudo-código.

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:   // Initializations 
3   dist[v] := infinity    // Unknown distance function from source to v 
4   previous[v] := undefined   // Previous node in optimal path from source 
5  dist[source] := 0      // Distance from source to source 
6  Q := the set of all nodes in Graph 
    // All nodes in the graph are unoptimized - thus are in Q 
7  while Q is not empty:     // The main loop 
8   u := vertex in Q with smallest dist[] 
9   if dist[u] = infinity: 
10    break       // all remaining vertices are inaccessible from source 
11   remove u from Q 
12   for each neighbor v of u:   // where v has not yet been removed from Q. 
13    alt := dist[u] + dist_between(u, v) 
14    if alt < dist[v]:    // Relax (u,v,a) 
15     dist[v] := alt 
16     previous[v] := u 
17  return dist[] 

Gracias

Answer 1

Relajación paso:

• Usted tiene dos nodos, u y v
• Por cada nodo tiene un distancia tentativa desde el nodo de origen (para todos los nodos excepto para la fuente, que comienza en infinito positivo y solo disminuye hasta alcanzar su mínimo).

La etapa de relajación básicamente está pidiendo esto:

• ya sé que puedo llegar a v con un poco de camino de la distancia dist[v]. ¿Podría mejorar esto yendo a v a través de u en su lugar? (Donde la distancia de este último sería dist[u] + weight(u, v))

Gráficamente:

s ~~~~~~~> v 
\  ^
    \  | 
    \~~~~~> u 

Se sabe poco de trayectoria s~>v que tiene distanciarse dist[v], y lo sabes un poco de trayectoria s~>u que tiene distanciarse dist[u]. Si dist[u] + weight(u, v) < dist[v], entonces la ruta s~>u->v es más corta que s~>v, ¡entonces será mejor que use esa!

(escribo a~>b a significar un camino de cualquier longitud a-b, mientras a->b me refiero a un solo borde directo a-b).

También es posible que desee comprobar esta conferencia: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

Answer 2

Uno de los significados de la palabra Inglés "relajación" está disminuyendo algo. Debido a que en las líneas 14,15 y 16 está comprobando esencialmente si puede disminuir (optimizar) la distancia calculada actualmente, supongo que es por eso que se llama "condición de relajación".