Złożoność czasowa i pamięciowa
Lekcja 7 z 9 w kursie Algorytm Dijkstry — algorytmy grafowe w Coddy.
Złożoność czasowa:
- O(V2 + V*E) w podanej tutaj wersji (w każdej z V rund przeglądane są wierzchołki w celu znalezienia minimum oraz krawędzie w celu relaksacji). Przy użyciu kopca binarnego i listy sąsiedztwa złożoność spada do O((V + E) log V).
Złożoność pamięciowa:
- O(V) dla tablic odległości i odwiedzonych wierzchołków (plus krawędzie wejściowe).
Podsumowanie:
- Algorytm Dijkstry wyznacza najkrótsze odległości od pojedynczego źródła dla nieujemnych wag, zachłannie zatwierdzając najbliższy wierzchołek i relaksując jego krawędzie.
- Nie działa w przypadku ujemnych krawędzi; w takich przypadkach użyj algorytmu Bellmana-Forda.
Spróbuj swoich sił
Ta lekcja nie zawiera wyzwania z kodem.
Sprawdź sięTa lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.
Wszystkie lekcje w sekcji Algorytm Dijkstry — algorytmy grafowe
2Algorytm
Jak to działa?PseudokodImplementacja (część 1)Implementacja (część 2)
Złożoność czasowa i pamięciowaPoćwicz samodzielnie: Kompilator C online