Najkrótsze ścieżki
Algorytm Edsgera Dijkstry z 1956 roku odwiedza węzły w kolejności skumulowanego kosztu od źródła, gwarantując optymalność na grafach o nieujemnych wagach krawędzi. Na siatce 1000 węzłów przetwarza w milisekundach; na rzadkich rzeczywistych sieciach drogowych obsługuje miliony węzłów przy odpowiednim strojeniu kolejki priorytetowej.
Wyszukiwanie ścieżki — Dijkstra i A*
Rysuj przeszkody na siatce i porównaj Dijkstrę (eksploruje równomiernie na zewnątrz) z A* (kierowanym heurystyką h(v)=‖v−cel‖ euklidesową). Wizualizuj front i zbiór zamknięty w czasie rzeczywistym.
Generowanie i rozwiązywanie labiryntów
Generuj labirynty za pomocą rekurencyjnego nawracania, zrandomizowanego MST Prima lub algorytmu Ellera wiersz po wierszu. Rozwiązuj za pomocą BFS (najkrótsza ścieżka), DFS (szybko, nieoptymalnie) lub A*.
Złożoność Dijkstry kontra A*
Dijkstra: O((V + E) log V) z kolejką priorytetową na kopcu binarnym
A*: O(b^d) w najgorszym przypadku; blisko O(E log V) przy dobrej heurystyce h(v)
Gwarancja A*: jeśli h(v) jest dopuszczalna (h(v) ≤ prawdziwy koszt), wynik jest optymalny
f(v) = g(v) + h(v), gdzie g = koszt od startu, h = heurystyka do celu
Drzewa rozpinające i spójność
Minimalne drzewo rozpinające (MST) łączy wszystkie węzły z minimalną łączną wagą krawędzi i bez cykli. Algorytm Kruskala sortuje wszystkie krawędzie według wagi i korzysta ze struktury zbiorów rozłącznych (union-find); algorytm Prima rozbudowuje jedno drzewo od węzła początkowego. Oba dają to samo MST, ale różnią się wydajnością na gęstych i rzadkich grafach.
Minimalne drzewo rozpinające
Dodawaj losowe węzły i obserwuj, jak algorytmy Kruskala i Prima budują MST krawędź po krawędzi. Zilustrowana kompresja ścieżek w strukturze union-find; porównaj liczbę krawędzi z pełnym klikiem.
Układ grafu sił skierowanych
Algorytm układu Fruchtermana-Reingolda — krawędzie działają jak sprężyny (prawo Hooke'a), węzły odpychają się siłą kulombowską. Samoorganizujący się układ ujawnia skupiska i węzły peryferyjne.
Optymalizacja kombinatoryczna
Niektóre problemy grafowe nie mają znanego algorytmu wielomianowego. Problem komiwojażera (TSP) — znalezienie najkrótszej trasy odwiedzającej każdy węzeł dokładnie raz — jest NP-trudny. Mimo to aproksymacje i heurystyki w praktyce działają zaskakująco dobrze.
Problem komiwojażera
Heurystyki 2-opt i najbliższego sąsiada dla TSP na 20–80 miastach. Porównaj chciwe wstawianie (szybkie, ~25% powyżej optimum) z symulowanym wyżarzaniem (wolniejsze, blisko optimum na 40 miastach).
Wizualizator algorytmów sortowania
Bubble sort, merge sort, quicksort, heapsort renderowane jako kolorowe słupki. Licznik inwersji wyświetlany w czasie rzeczywistym; porównaj czas rzeczywisty O(n²) kontra O(n log n) dla wejść n=50 do n=300.
Dlaczego A* przewyższa Dijkstrę w praktyce? Dijkstra rozszerza węzły równomiernie we wszystkich kierunkach. A* wykorzystuje heurystykę h(v), by ukierunkować rozszerzanie w stronę celu, eksplorując znacznie mniej węzłów. Na sieciach drogowych Dijkstra zazwyczaj eksploruje >50% grafu; A* z odległością euklidesową eksploruje <5% — bez utraty optymalności.
Ścieżki nauki
Ścieżka algorytmów klasycznych
- Wizualizator algorytmów sortowania
- Wyszukiwanie ścieżki — Dijkstra i A*
- Generowanie i rozwiązywanie labiryntów
- Minimalne drzewo rozpinające
Ścieżka zaawansowanych grafów
- Układ grafu sił skierowanych
- Problem komiwojażera
- Uczenie drzewa decyzyjnego