Úloha 10: Najkratšia cesta
Implementujte Dijkstrov algoritmus pre hľadanie najkratšej cesty v grafe.
Odovzdanie:
- Súbor
u10/najkratsia_cesta.pyodovzdajte do 27. 11. 2026 v systéme Traktor: U10: Najkratšia cesta.
Literatúra
- Magnus Lie Hetland, Python Algorithms: Mastering Basic Algorithms in the Python Language, 2. vydanie, Apress, 2014. Praktická kniha o návrhu a analýze algoritmov v Pythone; venuje sa klasickým algoritmom a obsahuje aj grafové témy. Informácie o knihe.
- Brad Miller a David Ranum, Problem Solving with Algorithms and Data Structures Using Python . Voľne dostupná učebnica s kapitolami o grafoch, BFS, Dijkstrovom algoritme a minimálnej kostre; vhodná na precvičovanie implementácie.
Video prednášky
- Lecture 9: Breadth-First Search — reprezentácia grafu, prehľadávanie do šírky a najkratšie cesty v neohodnotenom grafe.
- Lecture 13: Dijkstra — Dijkstrov algoritmus pre nezáporné váhy a riešený príklad.
Prednášky sú z kurzu Massachusetts Institute of Technology; sprievodné materiály kurzu obsahujú implementácie algoritmov v Pythone.