Algorytm Dijkstry w języku Java
Znajomość teorii grafów przydaje się do rozwiązywania wielu problemów dotyczących np. znajdowania najkrótszej ścieżki. Z zagadnieniem tym związany jest między innymi znany nam już algorytm Dijkstryalgorytm Dijkstry. Jak wiemy, jest to algorytm zachłanny – oznacza to, że na każdym etapie dokonuje on lokalnie najkorzystniejszego wyboru ścieżki, co prowadzi do znalezienia globalnie najlepszego rozwiązania, czyli najkrótszej ścieżki.
W tym e‑materiale zaimplementujemy algorytm Dijkstry w języku Java. Znajdziemy też najkrótszą ścieżkę w grafie ważonym.
Implementację tego algorytmu w pozostałych językach programowania znajdziesz w e‑materiałach:
Algorytm Dijkstry w języku C++Algorytm Dijkstry w języku C++,
Algorytm Dijkstry w języku PythonAlgorytm Dijkstry w języku Python.
Zaimplementujesz algorytm Dijkstry w języku Java.
Przeanalizujesz przykład wywołania algorytmu Dijkstry w języku Java.
Prześledzisz, jak przekształcić algorytm, aby działał dla różnych reprezentacji grafów.
Rozwiążesz problemy, w których wykorzystasz znajomość algorytmu Dijkstry i jego implementacji w języku Java.