Algorytmy grafowe i ich wymagania.

0

Dzień dobry,

mam takie malutkie pytanie do kogoś kto orientuje się w algorytmach grafowych a ściślej chodzi mi o algorytm najkrótszej ścieżki.

otóż poczytałem trochę na ten temat, ale żadne ze znalezionych źródeł nie było w stanie odpowiedzieć mi na to pytanie.

Proszę, o ile to możliwe , nie wklejać żadnych linków, bo siedzę juz 1,5 tygodnia i przeczytalem około 20 różnych możliwych implementacji i żadna nie pasuje do mojego projektu.

Otóż ,

chciałbym wiedzieć, co jest potrzebne do :

Algorytmu Djikstry ( on wyznacza DŁUGOŚĆ ścieżki od jednego wierzchołka do drugiego),

bo algorytm znajdowania ścieżki już mam i do niego jest ta długość potrzebna.

W moim projekcie mam :

tablicę połączeń ( 0 jak nie ma polaczenia, 1 jak jest pomiedzy dwoma wezlami sieci ) tablica dwuwymiarowa,

tablicę łuków sieci ( jeśli jest polaczenie z tablicy polaczen, to ten luk jest zainicjalizowany i istnieje w pamieci , w tej strukturze jest waga tego polaczenia )

ilosc lukow,

ilosc wezlow.

I tutaj pytanie końcowe,
co mi jeszcze będzie potrzebne, aby nie naładować projektu zbytnimi tablicami czy też wektorami, kontenerami, etc.

Liczę na wyczerpującą wypowiedź. Z góry dziękuję serdecznie i pozdrawiam.

0

masz wszystkie informacje potrzebne do wyliczenia najkrótszej ścieżki. zastanawiam się jak wygląda struktura przechowująca wagi. jeśli jest to coś w stylu trzy pola (wierzcholek poczatkowy, koncowy i waga) to nie jest to najlepszy pomysł. algorytm Dijkstry wymaga natychmiastowego dostępu do wagi między wierzchołkami. w tym przypadku złożoność by dramatycznie wzrosła, bo trzeba by przeszukać całą tablicę w poszukiwaniu wagi ( O(E) ). imho wygodniej by Ci było, gdybyś w tablicy połączeń trzymał wagi zamiast jedynek.
no i musisz jeszcze zaimplementować kolejkę priorytetową, w zależności czy masz graf rzadki (kopiec binarny) czy gęsty (tablica albo kopiec fibonacciego).

1 użytkowników online, w tym zalogowanych: 0, gości: 1