Czego się nauczysz
Nauczysz się liczyć najkrótsze drogi, gdy krawędzie mają różne długości: zatwierdzasz najbliższy wierzchołek i poprawiasz odległości jego sąsiadów.
Po co ci to na maturze
Grafy z odległościami są na maturze rzadkie, a algorytm Dijkstry wykracza poza podstawę programową. Przydaje się, gdy pytanie brzmi „ile kilometrów ma najkrótsza droga”, a nie „ile odcinków”.
Etapy lekcji
Spis lekcji
Teoria
4 rozdziałyNie zaczęte- 1.1Najmniej krawędzi to nie najbliżejGdy krawędzie mają długości, objazd może być krótszy niż droga na wprost.
- 1.2Zatwierdź najbliższyWierzchołek najbliżej startu spośród niezatwierdzonych ma już swoją ostateczną odległość.
- 1.3Którędy, a nie tylko ilePrzy każdej relaksacji zapisz, skąd przyszła lepsza droga. Potem idź po tych zapisach wstecz.
- 1.4PodsumowanieNajważniejsze rzeczy z każdego rozdziału na jednej stronie, do szybkiej powtórki.