Numero rilassamenti con algoritmo di Bellman e Ford

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Numero rilassamenti con algoritmo di Bellman e Ford #46248

avt
aristofane
Cerchio
Ciao a tutti, sto svolgendo degli esercizi e non riesco a capire il seguente esercizio sull'algoritmo di Bellman-Ford:

si consideri il seguente grafo (i pesi degli archi in questo caso ho evitato di inserirli)

grafo


Quanti rilassamenti esegue in totale l'algoritmo di Bellman e Ford con sorgente=c e considerando gli archi in ordine lessicografico?

La mia risposta sarebbe 1, ovvero l'unico rilassamento è:
D_{se}=D_{ss}+w(s,e) poi l'algoritmo termina, tuttavia la risposta sembra essere 0, cosa sbaglio?

Grazie in anticipo.
 
 

Re: Numero rilassamenti con algoritmo di Bellman e Ford #46335

avt
aristofane
Cerchio
Mi autorispondo, la soluzione è 1 infatti viene svolto un solo rilassamento con s=c si ha D_{se}=D_{ss}+w(c,e) dopodiché l'algoritmo termina non potendo essere visitati altri nodi.
Mea culpa.
Ringraziano: Omega, Ifrit

Re: Numero rilassamenti con algoritmo di Bellman e Ford #46369

avt
Omega
Amministratore
Ciao Aristofane, grazie per aver avuto la premura di risponderti e di condividere la soluzione con gli altri. emt
  • Pagina:
  • 1
Os