Qual è la condizione di rilassamento in teoria dei grafi

Question

sto cercando di capire i concetti principali della teoria dei grafi e gli algoritmi all'interno di esso. La maggior parte degli algoritmi sembra contenere una "condizione di rilassamento". Non sono sicuro di cosa sia.

Potrebbe qualcuno spiegare a me per favore.

Un esempio di questo è di Dijkstra algoritmo, qui è la pseudo-codice.

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[] 

Grazie

Answer 1

Relax passo:

• Hai due nodi, u e v
• Per ogni nodo, si dispone di una distanza tentativo dal nodo sorgente (per tutti i nodi tranne la fonte, si comincia all'infinito positivo e diminuisce solo fino a raggiungere il minimo).

Il passo relax fondamentalmente sta chiedendo questo:

• so già che posso raggiungere v con qualche percorso della distanza dist[v]. Potrei migliorare su questo andando invece a v tramite u? (Dove la distanza di quest'ultimo sarebbe dist[u] + weight(u, v))

Graficamente:

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

conoscete qualche percorso s~>v che ha distanza dist[v], e tu lo sai qualche percorso s~>u che ha distanza dist[u]. Se dist[u] + weight(u, v) < dist[v], allora il percorso s~>u->v è più breve di s~>v, quindi è meglio usare quella!

(scrivo a~>b significare un percorso di qualsiasi lunghezza da a a b, mentre a->b intendo un singolo bordo diretto a a b).

Si consiglia inoltre di controllare questa conferenza: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

Answer 2

Uno dei significati della parola inglese "relax" è in diminuzione qualcosa. Perché alle linee 14,15 e 16 si sta essenzialmente controllando se è possibile diminuire (ottimizzare) la distanza correntemente calcolata, suppongo che sia per questo che si chiami "condizione di rilassamento".