Szukanie najkrótszej drogi w grafie Opcje

[Shlizer]

Witam.
Mam pewien problem ze skryptem PHP, który chcę wykonać od kilku dni. Czuję się trochę jak ciemna masa, bo problem nie wydaje się skomplikowany, a mimo to nie mam pojęcia jak się do niego zabrać.

Ale do rzeczy.
Skrypt ma generować najkrótszą możliwą drogę w grafie na podstawie danych wejściowych - węzła początkowego i końcowego. Węzły są wrzucone do bazy danych i posiadają swój unikalny ID oraz opis. Istnieje też druga tabela opisująca ich relacje (węzeł1, węzeł2, które są połączone oraz ich wagę). Mam funkcję Szukaj(int,int), która przyjmuje wartości: ID źródła i ID ujścia.
Wiem, że dobrym sposobem będzie przeszukać kolejno najbliższe węzły źródła, zliczając ich poszczególne wagi, potem ich sąsiedztwo itd. aż trafimy na ujście. Następnie zebrać wszystkie trasy i wybrać tą o najmniejszej wadze. Jednak gdy przychodzi czas, żeby napisać kod, bladego pojęcia nie mam jak to zrobić.

Może mógłby ktoś mnie jakoś nakierować w jaki sposób wywoływać funkcje rekurencyjnie, jak przechowywać i tworzyć trasy, czy coś? =/
Może ktoś ma lepszy sposób na reprezentację tych danych, bo prawdę mówiąc za każdym razem trzeba sprawdzać, czy w połączeniu węzeł źródłowy jest reprezentowany jako węzeł1, czy węzeł2 w bazie..

Jeszcze jedno: skrypt też można zrobić na klasach, gdzie dane są po prostu wpisane w tablice / struktury danych, a ponieważ nie będą zmieniane można je wpisać na sztywno.
Dodatkowo jest taki problem, że nie wszystkie węzły są powiązane ze sobą na zasadzie jeden do jednego. Czasem jest to 'podróż w jedną stronę', ale wydaje mi się, że jak poradzę sobie z powyższym problemem to już z tym zagadnieniem nie powinno być kłopotu.

Jak są jakieś niejasności to chętnie odpowiem.

[ayeo]

Witam!

Jeśli mówisz o tzw Problemie Komiwojażera to pozostaje rekurencja. Matematycznie podobno nierozwiązywalny problem.Jest przewidziana ogromna nagroda dla osoby, która rozwiązałaby ten problem. CO do samej implementacji rekurencyjnej to wiedząc czego szukasz na pewno znajdziesz.

Pozdrawiam!