Dijkstra cu costuri negative pe muchii

[•Archazey]

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?

[•freak93]

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.

[•klamathix]

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.