Najlepszy Java Developer – Zadanie 7: Wyjazd na wakacje

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:

save image

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.

save image

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:

save image

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.