infoarena

Salut. As vrea va rog daca imi puteti spune cum pot gasi toate drumurile posibile intre 2 noduri dintr-un graf neorientat

Ai un numar infinit de drumuri posibile. Poate vrei sa zici numarul de drumuri de lungime minima. Merge cu un BFS.

De ce infinit? Adica,banuiesc ca se refera la drumuri in care sa nu treci de 2 ori prin acelasi nod.

Atunci merge sa faci o dinamica O(2 ^ N * N) ... dp[stare][nod] - numarul de posibilitati de a parcurge graful astfel incat sa pornesti din nodul de start, sa ajungi in nodul nod si sa ai in parcurgere nodurile din stare. Actualizezi starile urmatoare parcurgand vecinii nodului nod, care nu se afla deja in starea curenta. Rezultatul este suma de dp[stare][nodFinal]. Sunt curios daca exista o solutie mai buna :)

El nu a zis neaparat ca vrea numarul lor. Daca vrei sa gasesti drumurile propriu-zise, poti sa faci asta cu o parcurgere in adancime.

Iar daca le vrei pe cele de drum minim,inainte faci o parcurgere in latime si vezi care e distanta minima.

Eu vreau sa gasesc toate lanturile dintre un nod S si unul D. Nu cred ca este vorba de un infinit de posibilitati. Daca stiu sa fac asta voi putea adapta la unele probleme (toate drumurile minime sau suma costurilor pe toate lanturile de la sursa la destinatie,etc).
 

Incepi cu DF(S). Intr-un vector T marchezi faptul ca ai trecut prin S,iar intr-unul V adaugi elementul(va trebui sa iei si un k ce va creste de fiecare data). Iei toate nodurile i si daca S are legatura cu ele faci DF(i). Daca i=D,afisezi vectorul V. Nu uita ca la sfarsit sa faci T=0 si sa descresti k-ul.

Din ce am inteles eu mai sus fac o pargurgere DFS si retin nodurile in vect sirul V in ordinea in care le vizitez si in T le marchez ca vizitate. Insa nu inteleg cum imi va determine mie toate lanturile intre cele 2 noduri.

for(i=1;i<=n;i++) if(a[ x ][ i ]==1&&T==0) DF(i);

Intre doua noduri S si D exista un numar exponential de lanturi elementare. Backtracking e solutia ;).