Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> Szukanie najkrótszej drogi w grafie
Shlizer
post
Post #1





Grupa: Zarejestrowani
Postów: 24
Pomógł: 0
Dołączył: 4.09.2003
Skąd: z Gdyni

Ostrzeżenie: (0%)
-----


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.
Go to the top of the page
+Quote Post
 
Start new topic
Odpowiedzi
Shlizer
post
Post #2





Grupa: Zarejestrowani
Postów: 24
Pomógł: 0
Dołączył: 4.09.2003
Skąd: z Gdyni

Ostrzeżenie: (0%)
-----


Cytat(golaod @ 20.08.2009, 16:38:27 ) *
Sam sobie odpowiadasz na pytania:
google: algorytm prima i kruskala, minimalne drzewo rozpinające.

Wiem czym jest algorytm Dijkstry. Problem nie polega na wiedzy teoretycznej, ale na jej implementacji. Nie mam bladego pojęcia jak przedstawić niektóre rzeczy w kodzie (niektóre zrozumiałem po skryptach z innych języków). W Internecie przegrzebałem całą masę stron i nigdzie nie ma przykładu tego algorytmu dla php, dlatego pytam.
Tak swoją drogą - jak w php oznacza się nieskończoność? Rozumiem, że wystarczy bardzo duża liczba?

Edit: swoją drogą wierzchołki grafu nie znajdują się w żadnym układzie współrzędnych. Ich wagi to nie zawsze ich odległość, ale raczej koszt transportu i choć faktycznie im dalsza droga tym drożej, nie rośnie to tak, jak literki na osiach.

Cytat(dr_bonzo @ 20.08.2009, 17:43:53 ) *
To bl raczej algorytm A*/ do szukania drogi na "mapie kwadratow"

Widziałem ten temat i to z lekka inne zagadnienie w mojej opinii.

Ten post edytował Shlizer 20.08.2009, 21:54:28
Go to the top of the page
+Quote Post

Posty w temacie


Reply to this topicStart new topic
2 Użytkowników czyta ten temat (2 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Aktualny czas: 14.10.2025 - 19:00