Cosa significa "" nel contesto della teoria dei grafi? Mi sono imbattuto in questo mentre studiavo l'algoritmo di Dijkstra per il percorso più breve della singola fonte.Rilassamento di un fronte nell'algoritmo di Dijkstra
Here's una bella descrizione dell'algoritmo che spiega anche la nozione di rilassamento.
Il concetto di "rilassamento" deriva da un'analogia tra la stima del percorso più breve e la lunghezza di una molla elicoidale a trazione, che non è progettato per la compressione. Inizialmente, il costo del più breve percorso è sovrastimato, paragonato a una molla allungata. Quando vengono trovati percorsi più corti , il costo stimato viene ridotto e la molla è rilassata. Alla fine, il percorso più breve, se esiste, viene trovato e la molla è stata rilassata alla sua lunghezza di riposo.
Il processo di rilassamento nell'algoritmo di Dijkstra riferisce ad aggiornare il costo di tutti i vertici collegati ad un vertice v, se tali costi sarebbero migliorate includendo il percorso via v.
distensione un bordo, (un concetto puoi trovare anche in altri algoritmi di percorso più breve) sta cercando di ridurre il costo di raggiungere un vertice usando un altro vertice.
Si stanno calcolando le distanze da un vertice iniziale, ad esempio S, a tutti gli altri vertici. Ad un certo punto, hai risultati intermedi - stime attuali. Il rilassamento è il processo in cui si controlla, per alcuni vertici u e 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)
dove est(S,a) è la stima corrente della distanza, e dist(a,b) è la distanza tra due vertici che sono vicini nella grafico.
Cosa si sono fondamentalmente il check-nel processo di rilassamento è weather vostra stima corrente un-b potrebbe essere migliorata "deviando" il percorso attraverso c (questa "deviazione" sarebbe la lunghezza di un percorso da a a c e da c a b).