Algorytmy i struktury danych · Middle · Pytanie 59 z 75
Która struktura danych czyni algorytm Dijkstry wydajnym?
- ✓Poprawna odpowiedź: Kolejka priorytetowa (min-kopiec)
- 2Stos nieodwiedzonych wierzchołków
- 3Zwykła kolejka FIFO wierzchołków
Wyjaśnienie
Kopiec podaje najbliższy nieodwiedzony wierzchołek w O(log V). Ze zwykłą kolejką algorytm staje się BFS, który ignoruje wagi; przeglądanie wszystkich wierzchołków w poszukiwaniu minimum daje O(V²).