Algorytm Dijkstry w języku Python
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 Python.
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 JavaAlgorytm Dijkstry w języku Java.
Zaimplementujesz algorytm Dijkstry w języku Python.
Przeanalizujesz przykład wywołania algorytmu Dijkstry w języku Python.
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 Python.