Algorytmy i struktury danych · Middle · Pytanie 58 z 75
Co oblicza algorytm Dijkstry?
- ✓Poprawna odpowiedź: Najkrótsze ścieżki z jednego wierzchołka przy nieujemnych wagach
- 2Minimalne drzewo rozpinające grafu z wagami
- 3Najkrótsze ścieżki w dowolnym grafie, także z ujemnymi wagami
Wyjaśnienie
Wielokrotnie bierze nieodwiedzony wierzchołek o najmniejszej znanej odległości (z kolejki priorytetowej) i relaksuje jego krawędzie. Z kopcem binarnym działa w O((V + E) log V). Ujemne wagi go psują.