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.

[golaod]

Wszyscy mieszacie jakby to nie wiadomo co strasznego było:
Tworzysz Shlizer( dla algorytmu kruskala albo prima ) macierz sąsiedztwa:
A B C D
A -1 1 -1 -1
B 1 -1 3 2
C -1 3 -1 2
D -1 2 2 -1

(jak się wkradł błąd co do wag no to nie moja wina na szybko pisałem (IMG:style_emoticons/default/tongue.gif) )

I jak masz taką tablicę dwu wymiarową to zaznaczasz sobie wierzchołek startowy czytaj czy A czy B czy C czy D i tworzysz zbiór uporządkowany sąsiedztwa( od najmniejszej wagi ) następnie łączysz wierzchołek startowy z tym o najmniejszej wadze a do zbioru dodajesz sąsiedztwa nowego wierzchołka usuwając przy tym ze zbioru ten który się właśnie połączyło. Itd itd przy okazji sprawdzając czy węzły nie kierują się do tego samego wierzchołka.
na koniec funkcja array_sum na utworzonej tablicy drzewa spinającego i zadanie gotowe.

Ten post edytował golaod 24.08.2009, 12:30:46