|
Titlul: Dijkstra cu costuri negative pe muchii Scris de: Baltatu Andrei-Mircea din Octombrie 31, 2014, 13:05:29 Daca in loc de Bellman-Ford as folosi Dijkstra,crescand toate muchiile cu o valoare constanta astfel incat valorile sa fie toate pozitive,iar la sfarsit sa scad lungimeadrumului*constanta. Imi da raspunsul corect mereu?
Titlul: Răspuns: Dijkstra cu costuri negative pe muchii Scris de: Adrian Budau din Octombrie 31, 2014, 15:32:50 Nu:
Sa presupunem ca constanta ta e 5 (am folosit un numar la intamplare) Hai sa luam un triunghi, 3 muchii 1 -> 2, 1 -> 3 si 2->3. Daca muchia de la 1 la 3 are valoarea 5, muchie de la 1 la 2 valoarea 2 si muchia de la 2 la 3 tot valoarea 2 atunci cel mai bun drum de la 1 la 3 are distanta 4. Daca insa aduni 5 la toate, faci dijkstra si scazi la final lungime * 5 o sa iti dea ca distanta e 5 nu 4 (ti-ar fi iesit muchia 1->3 in loc cu distanta 5 + 5 = 10, in loc de 1 -> 2 + 2 -> 3 = (2 + 5) + (2 + 5) = 14). Daca incerci sa calculezi constanta pe baza celei mai mici muchii ca valoare te vezi izbii de aceasi problema. Titlul: Răspuns: Dijkstra cu costuri negative pe muchii Scris de: Mihai Calancea din Noiembrie 01, 2014, 04:05:56 Ca sa completez ce a zis Adi: e usor de văzut si fara example ca nu mai e aceeași problema. Noul tau cost e suma-costuri + nr-muchii * C, iar Dijkstra nu ti oferă niciun control asupra unui asemenea trade-off muchii-cost.
|