INF.04Algorytmika i Struktury Danych
Algorytmy Najkrótszej Ścieżki w Grafie (Dijkstra, Bellman-Ford)
Algorytmy wyznaczające trasę o najmniejszej sumarycznej wadze krawędzi między wierzchołkami w grafie ważonym (np. algorytm Dijkstry dla wag nieujemnych).
Wyznaczanie najkrótszej ścieżki w grafie
Problem polega na znalezieniu w grafie skierowanym lub nieskierowanym o ważonych krawędziach ścieżki łączącej wierzchołek źródłowy s z wierzchołkiem docelowym t, której suma wag krawędzi jest minimalna.
Kluczowe algorytmy na egzaminie:
- Algorytm Dijkstry (Dijkstra's Algorithm):
- Podejście zachłanne wykorzystujące kolejkę priorytetową.
- W każdym kroku wybiera wierzchołek o najmniejszym dotychczasowym dystansie i dokonuje relaksacji krawędzi wychodzących.
- Warunek konieczny: Wszystkie wagi krawędzi muszą być nieujemne (w ≥ 0)!
- Złożoność: O((V + E) log V) przy użyciu kopca binarnego.
- Algorytm Bellmana-Forda:
- Działa na grafach z ujemnymi wagami krawędzi.
- Pozwala na wykrycie cykli o ujemnej sumarycznej wadze (Negative Cycle).
- Złożoność: O(V · E).
- Algorytm Floyda-Warshalla:
- Wyznacza najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie (O(V³)).
Pułapki na egzaminie INF.04:
- Algorytm Dijkstry nie działa poprawnie dla krawędzi o wagach ujemnych; dla grafów z wagami ujemnymi należy zastosować algorytm Bellmana-Forda.
Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Algorytmy Najkrótszej Ścieżki w Grafie (Dijkstra, Bellman-Ford) lub rozpocznij trening.