Algorytm Dijkstry - najkrótsza ścieżka

Wprowadzenie

Algorytm Dijkstry to jeden z najważniejszych algorytmów w teorii grafów, wynaleziony przez Edsgera Dijkstrę w 1956 roku. Służy do znajdowania najkrótszej ścieżki od wierzchołka źródłowego do wszystkich pozostałych wierzchołków w grafie ważonym z nieujemnymi wagami.

Zastosowania: - Systemy nawigacji (GPS, mapy) - Routowanie w sieciach (IP, OSPF) - Systemy transportowe (optymalne trasy) - Gry komputerowe (pathfinding) - Planowanie tras lotniczych, kolejowych

Wymaganie: Wszystkie wagi krawędzi muszą być ≥ 0. Dla ujemnych wag używamy algorytmu Bellmana-Forda.

Idea algorytmu

Strategia zachłanna

Algorytm Dijkstry działa według strategii zachłannej (greedy):

  1. Na każdym kroku wybiera nieodwiedzony wierzchołek o najmniejszej znanej odległości
  2. "Relaksuje" wszystkie jego krawędzie wychodzące (aktualizuje odległości sąsiadów)
  3. Oznacza wierzchołek jako odwiedzony (finalny)

Kluczowa właściwość: Po odwiedzeniu wierzchołka, jego odległość jest optymalna i już się nie zmieni.

Wizualizacja krok po kroku

Graf:
    A --1-- B
    |     / |
    4   2   3
    | /     |
    C --1-- D

Źródło: A

Krok 0 (inicjalizacja):
  dist[A] = 0, dist[B] = ∞, dist[C] = ∞, dist[D] = ∞
  Nieodwiedzone: {A, B, C, D}

Krok 1 (odwiedź A, dist=0):
  Relaksacja:
    dist[B] = min(∞, 0+1) = 1
    dist[C] = min(∞, 0+4) = 4
  Nieodwiedzone: {B, C, D}

Krok 2 (odwiedź B, dist=1):
  Relaksacja:
    dist[C] = min(4, 1+2) = 3  ← lepsza!
    dist[D] = min(∞, 1+3) = 4
  Nieodwiedzone: {C, D}

Krok 3 (odwiedź C, dist=3):
  Relaksacja:
    dist[D] = min(4, 3+1) = 4 (bez zmiany)
  Nieodwiedzone: {D}

Krok 4 (odwiedź D, dist=4):
  Brak sąsiadów
  Nieodwiedzone: {}

Wynik końcowy:
  dist[A]=0, dist[B]=1, dist[C]=3, dist[D]=4

Algorytm Dijkstry - pseudokod

Dijkstra(graf G, wierzchołek źródłowy s):
    1. Dla każdego wierzchołka v:
        dist[v] = ∞
        prev[v] = NULL

    2. dist[s] = 0

    3. Utwórz kolejkę priorytetową Q zawierającą wszystkie wierzchołki
       (priorytet = dist[v])

    4. Dopóki Q nie jest pusta:
        a. u = Q.extract_min()  // Wierzchołek o najmniejszej dist

        b. Dla każdego sąsiada v wierzchołka u:
            i. alt = dist[u] + waga(u, v)
            ii. Jeśli alt < dist[v]:  // Relaksacja
                - dist[v] = alt
                - prev[v] = u
                - Q.decrease_key(v, alt)  // Aktualizuj priorytet

    5. Zwróć dist, prev

Złożoność: - Z prostą implementacją (lista): O(V²) - Z kolejką priorytetową (binary heap): O((V + E) log V) - Z Fibonacci heap: O(E + V log V)

Implementacja algorytmu Dijkstry

Implementacja podstawowa (O(V²))

Wyjście:

Odległości od A:
  A: 0
  B: 1
  C: 3
  D: 4

Implementacja z kolejką priorytetową (O((V+E) log V))

Rekonstrukcja najkrótszej ścieżki

Wyjście:

Najkrótsza ścieżka A → D:
  Ścieżka: A → B → C → D
  Odległość: 4

Dijkstra z pełną funkcjonalnością

Dijkstra krok po kroku - wizualizacja

Przykładowe wyjście:

=== Dijkstra krok po kroku ===

Inicjalizacja: start = A
  dist: {'A': 0, 'B': inf, 'C': inf, 'D': inf}

Krok 1: Odwiedzam A (dist=0)
  Relaksacja A → B:
    inf → 1 (przez A)
  Relaksacja A → C:
    inf → 4 (przez A)
  Kolejka PQ: [(1, 'B'), (4, 'C')]
  Odwiedzone: {'A'}

Krok 2: Odwiedzam B (dist=1)
  Relaksacja B → C:
    4 → 3 (przez B)
  Relaksacja B → D:
    inf → 4 (przez B)
  Kolejka PQ: [(3, 'C'), (4, 'C'), (4, 'D')]
  Odwiedzone: {'A', 'B'}

...

Praktyczne zastosowania

1. System nawigacji GPS

Wyjście:

=== System nawigacji GPS ===

Najkrótsza trasa Warszawa → Wrocław:
  Warszawa → Łódź → Wrocław
  Odległość: 345 km

Miasta w promieniu 300 km od Warszawy:
  Łódź: 135 km
  Kraków: 290 km

2. Routowanie w sieci komputerowej

Wyjście:

=== Routowanie w sieci ===

Tabela routingu dla R1:
Cel        Następny hop    Koszt
-----------------------------------
R2         R2              10
R3         R3              5
R4         R3              25
R5         R3              15

Ograniczenia algorytmu Dijkstry

Problem: Ujemne wagi

Dijkstra NIE działa poprawnie dla grafów z ujemnymi wagami!

Rozwiązanie: Użyj algorytmu Bellmana-Forda dla ujemnych wag.

Optymalizacje i warianty

1. Wczesne zakończenie (early termination)

Jeśli szukamy ścieżki tylko do jednego wierzchołka docelowego:

2. Heurystyka A* (rozszerzenie Dijkstry)

Algorytm A* to rozszerzenie Dijkstry z heurystyką (np. odległość euklidesowa):

Porównanie algorytmów najkrótszej ścieżki

Algorytm Złożoność Ujemne wagi Wszystkie pary Uwagi
BFS O(V + E) Nie Nie Tylko dla nieważonego (lub wagi=1)
Dijkstra O((V+E) log V) ❌ Nie Nie Najszybszy dla nieujemnych wag
Bellman-Ford O(V·E) ✅ Tak Nie Wykrywa cykle ujemne
Floyd-Warshall O(V³) ✅ Tak ✅ Tak Wszystkie pary wierzchołków
A* O((V+E) log V)* ❌ Nie Nie Dijkstra + heurystyka

*Zależne od heurystyki

Podsumowanie

Kluczowe cechy algorytmu Dijkstry

  • Strategia zachłanna - zawsze wybiera najbliższy wierzchołek
  • Kolejka priorytetowa - efektywne znajdowanie minimum
  • Złożoność O((V+E) log V) - szybki dla rzadkich grafów
  • Wymaga nieujemnych wag - ograniczenie!
  • Optymalna ścieżka - gwarantuje najkrótszą ścieżkę

Kiedy używać Dijkstry?

✅ Nieujemne wagi krawędzi ✅ Rzadkie grafy (E << V²) ✅ Pojedyncze źródło (od jednego wierzchołka) ✅ Systemy nawigacyjne ✅ Routowanie w sieciach

Co dalej?

Po opanowaniu algorytmu Dijkstry, następne kroki to:

  1. Lekcja 59: Minimalne drzewo rozpinające
  2. Algorytm Prima (podobny do Dijkstry!)
  3. Algorytm Kruskala

  4. Union-Find (Disjoint Set Union)

  5. Inne algorytmy ścieżek:

  6. Bellman-Ford (ujemne wagi)
  7. Floyd-Warshall (wszystkie pary)

  8. A* (gry, robotyka)

  9. Zaawansowane tematy:

  10. Przepływy w sieciach
  11. Dwukierunkowy Dijkstra
  12. Contraction Hierarchies (mapy)

Zadania praktyczne

Zadanie 1: K najkrótszych ścieżek

Zmodyfikuj Dijkstrę aby znaleźć K najkrótszych ścieżek (nie tylko jedną najkrótszą).

Zadanie 2: Ścieżka z ograniczeniami

Znajdź najkrótszą ścieżkę, która przechodzi przez maksymalnie K wierzchołków pośrednich.

Zadanie 3: Wizualizacja

Stwórz wizualizację graficzną algorytmu Dijkstry pokazującą kolejne kroki.

Zadanie 4: Porównanie wydajności

Porównaj wydajność Dijkstry z BFS dla grafu z jednostkowymi wagami.

Następna lekcja: Minimalne drzewo rozpinające - algorytmy Prima i Kruskala

Wróć do spisu lekcji