Algorytm Dijkstry w języku C++
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 C++.
Implementację tego algorytmu w pozostałych językach programowania znajdziesz w e‑materiałach:
Algorytm Dijkstry w języku JavaAlgorytm Dijkstry w języku Java,
Algorytm Dijkstry w języku PythonAlgorytm Dijkstry w języku Python.
Zaimplementujesz algorytm Dijkstry w języku C++.
Przeanalizujesz przykład wywołania algorytmu Dijkstry w języku C++.
Przeanalizujesz, 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 C++.