[C] Szukanie drogi w grafie

[PeWuEr]

Witam.

Chce napisać algorytm szukania drogi w grafie. Tzn. czy istnieje połączenie w grafie skierowanym miedzy wierzchołkiem 'a' a wierzchołkiem 'b'. Graf mam zrobiony na tablicach. Mam 3 struktury. Żeby to lepiej wyobrazić wrzucę kod headera:

Kod: Zaznacz cały

typedef struct
{
  char *_id;
  char *_id_luku;
} str_sasiad;


typedef struct 
{
  int _ilosc;
  str_sasiad *_sasiad;
  char *_id;
} str_wierz;


typedef struct 
{
  int _ilosc;
  str_wierz *_wierz;
} str_graf;

Mam napisane wszystko inne czyli dodawanie, usuwanie wierzchołków i łuków, szukanie luku pomiędzy dwoma wierzchołkami, szukanie czy wierzchołek ma sąsiada itd.

Ale kurde nie mam pojecia jak zrobic szukanie drogi. Myślałem o Dijkstry, ale nie mogę go w żaden sposób zaimplementować, bo zwyczajnie nie wiem jak niestety i go nie rozumiem. Więc może wybór padnie na algorytm Floyda bo wydaje mi sie najlepszym rozwiazaniem. Pierwszym problemem jaki mnie spotyka to wagi grafu i wszystko co dalej z tym zwiazane. Prosilbym o jakas pomoc, chociaz w pseudokodzie.

[zhtk]

Po co takie ciężkie działa? Nie lepiej puścić lekko podrasowanego DFSa? W skrócie: robisz tablicę bool visited[liczba wierzchołków]. Potem robisz stos, na który będziemy odkładać kolejne wierzchołki ze znalezioną drogą. Dla wierzchołka A puszczasz DFSa. Kiedy dojdzie on do wierzchołka B, odkładasz B na stos a DFS zwraca true; Wtedy DFS na wyższym poziomie też odkłada swój wierzchołek na stos i zwraca true. I tak dalej, aż dojdziesz do A. Wtedy na stosie będzie się znajdowała lista wierzchołków, które prowadzą do B. Nie muszę mówić co to DFS i że jest to funkcja rekurencyjna?