Szukanie najkrótszej drogi w grafie [inaczej]

0

Witam !

Stanąłem oto przed takim problemem. Za zadanie mam obliczyć najkrótszą drogę z każdego spośród pierwszych dwudziestu wierzchołków do każdego z pozostałych pierwszych dwudziestu wierzchołków w danym grafie (nieskierowanym). Graf ma jednak dużo wiecej wierzchołków (maks. 20000) i oczywiscie moze zajsc sytuacja ze najkrótsza droga np. z wiercholka 5 do 18 prowadzi przez wierzcholek nr. 17564 :/ . Idealnie pasowałby do tego algorytm Roya - Warshalla. Niestety pojawia sie pewien problem. Maksymalna ilosc pamieci jaką moge wykorzytsac (ograniczenie dotyczy stosy, sterty itd.) to 64 Mb. W przypadku grafu o 20000 wierzchołków deklarując tablice dwuwymiarową int t[20000][20000] zużywam jakies 20000 20000 4 / (1024 * 1024) Mb co daje nam około ponad 1000 Mb [???]

Czy ktoś zna inną metode która moglaby mi pomoc</b>

0

A nie możesz po prostu puścić DFS(lub BFS) dla każdego z 20 wierzchołków? to rozwiązanie liniowe i pamięci też potrzebuje tyle co jest danych. Nie napisałeś żeby to był graf z wagami więc nie wiem skąd tutaj warshall?

0

niewiem czy Cie dobrze rozumiemale jezeli tak to poszukaj w necie "problemu komiwojazera" SSN mialem gdzieś to opisane ale nie moge znaleŹć pozdr

0
t4iglo napisał(a)

Niestety pojawia sie pewien problem. Maksymalna ilosc pamieci jaką moge wykorzytsac (ograniczenie dotyczy stosy, sterty itd.) to 64 Mb. W przypadku grafu o 20000 wierzchołków deklarując tablice dwuwymiarową int t[20000][20000] zużywam jakies 20000 20000 4 / (1024 * 1024) Mb co daje nam około ponad 1000 Mb [???]

Sąsiednie wierzchołki można trzymać też w liście! Zatem będzie tyle list co wierzchołków.

0

Jest to graf z wagami, a moim celem jest znalezienie najkrótszej drogi z wierzcholka 1 do wierzchołka N przechodzącego przez pierwsze 20 wierzchołków.

Sorry za nieścislości

Dodam jeszcze że graf jest cykliczny.

0

Ładnie to tak oszukiwać? Na OI zadania należy rozwiązywać samodzielnie.

0

Nie oszukuje :)
Sam algorytm już napisałem, zastanwiam się tylko jak liczyć drogi w grafie między niesąsiednimi węzłami bez przekraczania limitu pamieci...

Zadanie na OI wyglada inaczej, ma dodatkowo wymagania co dokolejnosci poruszania sie w grafie itd. itd. Ja pytałem tutaj tylko o aspekt pamięci. Nie mam zamiaru publikować czyjegoś gotowego rozwiązania.

0

Warshalla chyba nie da się wprost( albo i <ort>w ogóle</ort>) zrobić na listach sąsiedztwa ale Dijkstre tak, jeżeli graf ma wagi ujemne to należy go odpowiednio przerobić - poszukaj w internecie. Powiem tylko że metoda typu dodanie do każdej wagi pewnej liczby X aby wszystkie były dodatnie nie zadziała i trzeba poszukać ;)
Dijkstra ma złożoność taką że powinna szybko przerobić podany przez Ciebie rozmiar danych

0

Ludzie, bez "czitowania", to jest test Waszych umiejętności, a nie naszych. W koszu powinno wylądować bez gadania.

0

no właśnie - umiejętnoście, a nie wiedzy!! niektórzy mają w szkole nauczycieli co tylko popatrzą na zadania z oi i <ort>Od razu</ort> to co sie może przydać przerabiają na lekcjach, a inni uczniowie muszą uczyć się sami i szperać po książkach i w internecie.

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