Ćwiczenie: Najkrótsza droga po polskich miastach
Celem ćwiczenia jest ręczne zbudowanie grafu w aplikacji graphonline, a następnie uzupełnienie kodu w Pythonie, który znajdzie najkrótsze połączenie między wybranymi miastami za pomocą algorytmu Dijkstry.
Część 1: Szkicowanie grafu w aplikacji
-
Otwórz w przeglądarce stronę: https://graphonline.top/pl/
-
Korzystając z narzędzi po lewej stronie (dodawanie wierzchołków i krawędzi), naszkicuj graf przedstawiający połączenia drogowe między podanymi miastami. Postaraj się rozmieścić miasta mniej więcej tak, jak leżą na rzeczywistej mapie Polski (Gdańsk na północy, Kraków na południu itd.).
Lista miast (wierzchołków):
-
Gdańsk
-
Warszawa
-
Poznań
-
Wrocław
-
Kraków
-
Katowice
-
Łódź
Połączenia drogowe (krawędzie) z odległościami (w km):
-
Gdańsk – Warszawa: 340
-
Gdańsk – Poznań: 300
-
Warszawa – Łódź: 140
-
Warszawa – Kraków: 300
-
Łódź – Wrocław: 200
-
Poznań – Wrocław: 180
-
Wrocław – Kraków: 270
-
Kraków – Katowice: 80
Wskazówka: Aby dodać krawędź z wagą (odległością), po narysowaniu linii między miastami pojawi się okno, w którym wpiszesz odpowiednią liczbę kilometrów. Umieść miejscowości zgodnie z ich położeniem na mapie Polski.
Część 2: Uzupełnianie kodu w Pythonie
Poniższy kod znajdowania najkrótszej drogi jest już prawie gotowy. Musisz jednak uzupełnić go w kilku miejscach, oznaczonych komentarzami # UZUPEŁNIJ: … .Wykorzystaj graf, który przed chwilą narysowałeś.
Zadania do wykonania
- Wyeksportuj graf ze strony https://graphonline.top/pl/ jako SVG.
-
Uzupełnij graf w słowniku graf_polski o brakujące połączenia dla Wrocławia, Katowic i Łodzi.
-
Uzupełnij kod w funkcji dijkstra w miejscach oznaczonych # UZUPEŁNIJ .
-
Przetestuj działanie algorytmu dla podanych przykładów.
-
Samodzielnie napisz kod dla przykładu 3. (Wrocław → Warszawa) i sprawdź, czy wynik zgadza się z tym, co pokazałoby narzędzie graphonline, gdybyś użył jego wbudowanej funkcji „Znajdź najkrótszą ścieżkę używając algorytmu Dijkstra”.
Was this helpful?
0 / 0