Kolokwium: Dijkstra

Algorytm Dijkstry

Algorytm służący do znajdowania najkrótszych ścieżek w grafach z nieujemnymi wagami krawędzi.

Waga krawędzi w grafie

Wartość przypisana krawędzi, określająca koszt lub odległość między dwoma wierzchołkami.

Graf

Zbiór wierzchołków połączonych krawędziami, które mogą mieć różne wagi.

Wierzchołek

Podstawowy element grafu, reprezentujący obiekt lub punkt w strukturze.

Termin 'najkrótsza ścieżka'

Ścieżka w grafie, której suma wag krawędzi jest minimalna.

Typy grafów

- Niezorientowane - Zorientowane - Ważone - Nieważone

Złożoność czasowa algorytmu Dijkstry

W zależności od zastosowanej struktury danych: O(V^2) lub O(E + V log V).

Pseudokod algorytmu Dijkstry

1. Inicjalizuj węzły 2. Wybierz węzeł z najmniejszym kosztem 3. Uaktualnij koszty sąsiadujących węzłów 4. Powtarzaj do zakończenia

Algorytm Bellmana-Forda vs Dijkstry

Bellmana-Forda obsługuje ujemne wagi, Dijkstra - tylko nieujemne.

Przykład zastosowania Dijkstry

Używany w nawigacji GPS do wyznaczania najkrótszej trasy.

Dijkstra a BFS

BFS znajduje najkrótsze ścieżki w grafach nieważonych, Dijkstra w ważonych.

Użycie kopca w Dijkstrze

Zwiększa wydajność algorytmu do O(E + V log V) przez optymalizację wyboru węzłów.

Stan węzła w algorytmie

Węzeł może być: nieodwiedzony, odwiedzony, lub oznaczony jako najkrótsza ścieżka.

Zastosowania algorytmu Dijkstry

- Nawigacje - Analiza sieci - Teleinformatyka - Grafika komputerowa

Prawda czy fałsz: Dijkstra działa na grafach z ujemnymi wagami.

Fałsz, ponieważ algorytm Dijkstry nie jest przystosowany do ujemnych wag.

Porównanie Dijkstry z A*

A* jest bardziej efektywny w poszukiwaniu ścieżek w zastosowaniach, które mają heurystykę.

Uzupełnij zdanie: Algorytm Dijkstry korzysta z ___ do ustalania kolejności węzłów.

Kopca (min-heap) lub tablicy.

Różnica między algorytmem Dijkstry a Floyd-Warshall

Dijkstra znajduje najkrótsze ścieżki z jednego węzła do innych, Floyd-Warshall dla wszystkich par węzłów.

Wykres kosztów przy Dijkstrze

Koszty są aktualizowane w miarę przetwarzania węzłów.

Wady algorytmu Dijkstry

Wydajność spada dla gęstych grafów oraz ograniczenia w przypadku ujemnych wag.