|
Titlul: Graf neorientat ponderat Scris de: Flaviu Manica din 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? :? Titlul: Răspuns: Graf neorientat ponderat Scris de: Paul-Dan Baltescu din 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 (http://htttp://infoarena.ro/problema/apm).
|