Algorithmen und Datenstrukturen · Middle · Frage 59 von 75
Welche Datenstruktur macht Dijkstras Algorithmus effizient?
- 1Eine Priority Queue (Min-Heap)
- 2Ein Stack unbesuchter Knoten
- 3Eine einfache FIFO-Queue von Knoten
Antwort zeigen
Richtige Antwort: Eine Priority Queue (Min-Heap)
Erklärung
Der Heap liefert den nächstgelegenen unbesuchten Knoten in O(log V). Mit einer einfachen Queue wird der Algorithmus zu BFS, das Gewichte ignoriert; alle Knoten nach dem Minimum zu durchsuchen macht ihn O(V²).