Ragazzi sto studiando l'algoritmo di bellman-ford sui cammini minimi e non riesco proprio a capirlo...qualcuno di voi sa dirmi in parole povere(non tecniche) come funziona?
grazie anticipatamente!
Ragazzi sto studiando l'algoritmo di bellman-ford sui cammini minimi e non riesco proprio a capirlo...qualcuno di voi sa dirmi in parole povere(non tecniche) come funziona?
grazie anticipatamente!
Ciao,
innanzi tutto hai capito a cosa serve? Lo scopo è quello di definire, dato un grafo, il percorso a costo minimo per raggiungere ciascun nodo (fissato un nodo di partenza).
Hai un grafo fatto di nodi e archi che li uniscono. Ad ogni ARCO è associato un costo.
Si parte dal dare al NODO sorgente valore 0 e valore infinito a tutti gli altri.
L'idea è quella di partire dal nodo sorgente e cominciare a guardare i nodi adiacenti, cioè che distano un passo solo. Si assegna loro il valore del costo per raggiungerli (determinato dal costo dell'arco + il valore del nodo da cui si è partiti, che in sto caso è 0 visto che stiamo partendo dalla sorgente). A questo punto per ciascuno dei nodi raggiunti ragiono allo stesso modo: guardo i nodi che gli distano uno e assegno loro il valore dell'arco che ho percorso per raggiungerli più quello che avevo già assegnato al nodo da cui ora sono partito (assegno loro il nuovo valore solo se è più piccolo di quello che già avevano: la prima volta che li raggiungi è certamente più piccolo in quanto abbiamo detto che inizialmente diamo a tutti i nodi valore infinito). Ad ogni passaggio i nodi raggiunti lo step precedente (considera nodi raggiunti solo quelli a cui hai aggiornato il valore) diventano punto di partenza per raggiungere i nodi adiacenti il cui valore diventa (SE è minore di quello che già possiedono) quello dell'arco percorso per raggiungerli + il valore del nodo da cui li si è raggiunti (e in tal caso diventano a loro volta nuovi punti di partenza). Mi sto ripetendo per darti l'idea dell'iterazione che fa questo algoritmo.
Se il grafo ha N nodi sei certo che dopo N-1 giri tutti i nodi hanno a loro assegnato il costo minimo per essere raggiunti dal nodo sorgente. Ovviamente ad ogni giro quando aggiorni il valore di un nodo devi salvarti il percorso associato per raggiungerlo dalla sorgente, così quando avrai finito le iterazioni oltre ad avere tutti i costi minimi avrai anche i percorsi associati cioè i percorsi a costo minimo per raggiungere ogni nodo del grafo dal nodo sorgente.
Se non ti è chiaro proviamo a far un esempio...
Ciao!
grazie mille!
chi mi può fare un esempio?
grazie
Non riesumiamo thread morti e sepolti...
Amaro C++, il gusto pieno dell'undefined behavior.
Permessi di invio
