Informatik Algorithmen – Dijkstra und kürzeste Wege
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Welches Problem löst der Dijkstra-Algorithmus? · Was ist die Invariante von Dijkstra …
Karten
15 KartenWelches Problem löst der Dijkstra-Algorithmus?
Rückseite
Er findet die kürzesten Pfade von einem Startknoten zu allen anderen Knoten in einem Graphen mit nicht-negativen Kantengewichten.
Was ist die Invariante von Dijkstra während der Ausführung?
Rückseite
Für alle Knoten in der besuchten Menge ist die finale kürzeste Distanz bereits bestimmt und wird nicht mehr geändert.
Wie lautet die Initialisierung der Distanzwerte?
Rückseite
Distanz des Startknotens = 0, alle anderen Knoten = unendlich (∞); alle Knoten sind unbesucht.
Was passiert bei der Relaxierung einer Kante (u,v)?
Rückseite
Wenn dist[u] + w(u,v) < dist[v], wird dist[v] auf diesen kleineren Wert aktualisiert und v erhält u als Vorgänger.
Welche Datenstruktur realisiert die effiziente Extraktion des Minimums?
Rückseite
Eine Prioritätswarteschlange (Min-Heap) speichert (Distanz, Knoten) und liefert den unbesuchten Knoten mit minimaler Distanz in O(log V).
Wie oft wird jeder Knoten maximal aus der Priority Queue extrahiert?
Rückseite
Einmal, da nach Extraktion die finale Distanz feststeht und der Knoten als besucht markiert wird.
Wie oft kann eine Kante maximal relaxiert werden?
Rückseite
Einmal pro Richtung, also maximal einmal bei gerichteten Graphen, da nur der Startknoten der Kante die Relaxierung auslöst.
Wie lautet die Laufzeit mit Binärheap?
Rückseite
O((V + E) log V): V Extraktionen und bis zu E Decrease-Key-Operationen, jede in O(log V).
Warum funktioniert Dijkstra nicht mit negativen Kantengewichten?
Rückseite
Negative Gewichte können nach Extraktion eines Knotens noch kürzere Pfade erzeugen, was die Invariante verletzt.
Welcher Algorithmus löst kürzeste Pfade bei negativen Gewichten?
Rückseite
Bellman-Ford-Algorithmus in O(V·E), der auch negative Zyklen detektieren kann.
Was speichert der Vorgänger-Array (prev) bei Dijkstra?
Rückseite
Für jeden Knoten den direkten Vorgänger auf dem kürzesten Pfad vom Startknoten – ermöglicht Pfadrekonstruktion rückwärts.
Wie unterscheidet sich A* von Dijkstra?
Rückseite
A* nutzt eine Heuristik h(v) zur Zielführung: f(v) = g(v) + h(v); bei h ≡ 0 wird A* zu Dijkstra.
Wann ist Dijkstra schneller als Bellman-Ford?
Rückseite
Bei Graphen ohne negative Gewichte: O((V+E) log V) vs. O(V·E), besonders bei dichten Graphen deutlich effizienter.
Was bedeutet 'Decrease-Key' im Kontext von Dijkstra?
Rückseite
Aktualisierung der Priorität eines Knotens in der Queue nach erfolgter Relaxierung auf einen kleineren Distanzwert.
Wie rekonstruierst du den kürzesten Pfad nach Dijkstra?
Rückseite
Starte beim Zielknoten, folge prev[] rückwärts bis zum Startknoten, kehre die Reihenfolge um – ergibt den Pfad in Vorwärtsrichtung.