infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Graf neorientat ponderat
Pagini: [1]   În jos
« mesajul precedent următorul mesaj »
  Imprimă  
Ajutor Subiect: Graf neorientat ponderat  (Citit de 1148 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
•flaviumanica
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« : Februarie 03, 2013, 14:56:21 »
Buna ziua! Am si eu o nelamurire la o problema: Se citesc date despre un GN ponderat.Care este cea mai scurta lungime a unui circuit,care sa nu treaca de 2 ori prin aceeasi muchie?
Daca nu ar fi fost ultima conditie,cea mai scurta era 2*muchia de cost cel mai mic,dar asa?  Confused
Memorat
•pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #1 : Februarie 03, 2013, 15:46:34 »
O solutie ar fi sa sortezi muchiile dupa ponderea asociata. Initial, presupui ca graful nu are nici o muchie si le adaugi treptat in noua ordine. Cand o muchie noua inchide un ciclu ai gasit ciclul de cost minim. Algoritmul e similar cu cel de determinare a arborelui partial de cost minim.
Memorat
Am zis Mr. Green
Pagini: [1]   În sus
  Imprimă  
infoarena > infoarena - concursuri, probleme, evaluator, articole > Informatica > Subiect: Graf neorientat ponderat
 « mesajul precedent următorul mesaj »
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines