Zadanie
Pomyślicie, że 6 zadanie nie zostało jeszcze sprawdzone, a wyskakuje już z kolejnym. Niestety nastała taka sytuacja – oczywiście wynikła od Pablo. Ma on poważny problem – chce zorganizować wypad na małe wakacje. Ma niestety sporo propozycji wyjazdu i największym priorytetem jest odległość. Musi wybrać to naprawdę szybko. Klikanie i wpisywanie np. w Google Maps go nie urządza, potrzebuje czegoś lepszego.
Zadeklarował się on dostarczyć mapę możliwych dojazdów na dane miejsce wypoczynkowe dla każdej z propozycji wyjazdu. Poda on również miejsce, z którego rusza oraz cel jego podróży. Oczekuje za to otrzymania odległości najkrótszej trasy dla danej propozycji wyjazdu.
Zanim proszę Cię o wykonanie takiej prostej aplikacji oczywiście zgłębiłem trochę temat wyliczania takiej trasy. Okazało się, że można to zrobić np. używając algorytmu Dijkstry.
Algorytm może się bardzo dobrze sprawdzić, w końcu mapę danej propozycji otrzymamy w formie tzw. macierzy sąsiedztwa. Jest to po prostu tablica dwuwymiarowa, gdzie wartości oznaczają odległości między danymi punktami grafu.
Graf – czyli zbiór wierzchołków połączonych krawędziami będziemy identyfikować z mapą dojazdu – w końcu tak jak na mapie dane miasta/miejscowości są połączone ustaloną drogą. Dokładniej będziemy mieli do czynienia z grafem ważonym – czyli grafem, gdzie każda krawędź ma ustaloną wagę – w naszym przypadku będzie to odległość między miastami.
Aby lepiej zrozumieć tą koncepcję przypuśćmy, że mamy o to taki graf:
Na krawędziach mamy opisane wagi (odległości) między miastami. Czyli między Wrocławiem, a Warszawą mamy wagę 11 – czyli tyle kosztuje nas przejście z jednego miasta do drugiego.
Dodatkowo graf jest skierowany – czyli z jednego wierzchołków do drugiego możemy przejść, lecz z powrotem już nie. Takim przykładem jest Warszawa – Łódź, z Warszawy możemy jechać do łodzi kosztem 3, zaś z Łodzi do Warszawy musimy już jechać na około (przez inne wierzchołki – miasta).
Powyższe miasta możemy również opisać liczbami od 0 do n – co pozwoli nam użyć ich jak indeksów w tablicy.
Teraz tworzymy tablicę dwuwymiarową używając powyższych indeksów:
-1 3 -1 11 5 -1 -1 5 -1 -1 -1 5 -1 -1 1 11 -1 -1 -1 -1 5 -1 1 -1 -1 -1
Każdy wiersz w tablicy odpowiada wierzchołkowi początkowemu, zaś każda kolumna odpowiada wierzchołkowi końcowemu. Pierwsza wartość -1 oznacza, że nie ma połączenia między wierzchołkami (czyli z wierzchołka 0 do wierzchołka 0 nie możemy przejść bezpośrednio). Lepszym przykładem będzie wartość 3 – czyli bierzemy indeks wiersza (czyli ruszamy z 0) oraz indeks kolumny (1 – tam trafimy) i wpisujemy wartość połączenia między wierzchołkiem 0, a 1 – jest to oczywiście 3.
Dla potrzeby przykładu użyłem -1, aby oznaczyć brak wystąpienia bezpośredniego połączenia.
Przygotowałem również dla Ciebie szablon, do którego będziesz mógł dokleić swoją implementację. Możesz tworzyć klas ile tylko chcesz, ważne, aby zostały w finalnym rozwiązanie te klasy, które Ci przekazałem. 😉
Przykład
Wszystko co napisałem powyżej może być lekko zagmatwane – zróbmy prosty przykład.
Mamy graf miast:
Aplikacja otrzymuje trzy informacje:
- graf w postaci macierzy sąsiedztwa, czyli:
-1 3 -1 11 5 -1 -1 5 -1 -1 -1 5 -1 -1 1 11 -1 -1 -1 -1 5 -1 1 -1 -1 -1
- wierzchołek początkowy
- wierzchołek końcowy
Naszym celem jest wyznaczenie najkrótszej drogi z Lublina do Wrocławia. Na grafie łatwo zauważyć, że trasa będzie wyglądała następująco:
Lublin -> Białystok -> Warszawa -> Wrocław
A cała trasa ma długość 17. Taką wartość właśnie powinna zwrócić nam aplikacja.
Punktacja
Przygotowane jest 10 testów, za każdy test otrzymasz 150 punktów. Łącznie można zyskać 1500 punktów.
Porady
- Napisz co najmniej trzy testy: trasa istnieje, nie istnieje, punkt docelowy jest w punkcie startowym,
- Gdy coś nie jest jasne to pytaj,
- Zanim zaczniesz pisanie kodu zapoznaj się z algorytmej i spróbuj go najpierw użyć na kartce. Stwórz prosty graf i przejdź krok po kroku według wskazówek algorytmu,
- Ciekawą wizualizację Dijkstry znajdziesz tutaj,
- Można użyć innych algorytmów, jeśli tylko zechcesz,
- Pamiętaj o tym, że -1 oznacza brak krawędzi między wierzchołkami.
Czas
Zadanie zostało opublikowane 21 stycznia, a jego rozwiązania można przesyłać do 31 stycznia do godziny 23.59. Zadania wysłane później będą automatycznie usuwane.
Format
Zadanie należy wysłać na email: njd@1024kb.pl z tematem: TWÓJ-NICK_HOLIDAYS.
Zadanie przesyłamy jako repozytorium Git – może być hostowany na GitHub, GitLab, Bitbucket – gdzie tylko chcesz. W wiadomości podajemy tylko link do repozytorium projektu. 😉
Pamiętajcie, aby do pliku .gitignore dodać:
- /target
- /out
- /.idea
- *.iml
I inne pliki/katalogi, które nie powinny być na zdalnym repozytorium.
W razie jakichkolwiek wątpliwości pytajcie jak ma wyglądać finalna aplikacja. 😉
Rozwiązanie
Rozwiązanie zadania można znaleźć w tym repozytorium.
