Numarul drumurilor de cost minim

[•darkseeker]

Am o problema in a determina cate noduri de cost minim sunt intre 2 noduri din graf . Daca poate cineva as dori sa-mi explice ce gresesc . Deci fac dijkstra , caut nodul de cost minim , iar apoi verific nu doar daca imbunatateste costul ci si daca duce catre un cost minim egal cu nodul curent . In caz de imbunatatire atunci numarul drumurilor minime de la sursa la nodul curent este egal cu numarul drumurilor minime d la sursa la nodul de cost minim . In caz de egalitate numarului drumurilor minime d la sursa la nodul curent ii adaug numarul drumurilor minime de la sursa la nodul d cost minim. La inceputul algoritmului initializez numarul drumurilor de cost minim de la sursa la vecini cu 1 si de la sursa la sursa cu 1.

[•S7012MY]

Daca nu ai nevoie de eficienta cred ca cea mai buna varianta ar fii sa faci un roy-floyd

[•darkseeker]

Am nevoie de eficienta ... trebuie sa-mi intre in timp

[•gabitzish1]

Am o problema in a determina cate noduri de cost minim sunt intre 2 noduri din graf .

Ai nevoie de cate noduri de cost minim sau de cate drumuri ?
Daca ai nevoie de noduri, s-ar putea de exemplu sa ai un nod cu cost foarte mic, dar care sa fie pe un drum cu cost foarte mare.