12 mai 2010

Toate drumurile intre doua noduri

Un algoritm simplu pentru determinarea tuturor cailor pe care se poate ajunge de la un nod la altul intr-un graf:

List p; // o lista curenta
PathList x; // un vector cu toate caile posibile
Nod s, d; // sursa, destinatie

PathFind (Nod c) {

p = p U c; //adauga nodul curent la sfarsitul listei
Pentru fiecare nod v adiacent cu c {
Daca (v==d) atunci
Salveaza lista p in x;
Altfel
daca (v nu e in p)
PathFind(v);
}
Sterge ultima poz din p;
}

Niciun comentariu: