Tutorium 9 SSSP

Was ist der Hauptgrund, dass in Dijkstras Algorithmus in jedem Schritt der nicht besuchte Knoten mit der kleinsten vorläufigen Distanz ausgewählt wird zur weiteren Verarbeitung?

• Um die Anzahl der Operationen zu minimieren und die Effizienz des Algorithmus zu verbessern

• Um Graphen mit negativen Kantengewichten effektiv zu verarbeiten.

• Weil diese Auswahl garantiert, dass der kürzeste Pfad zu diesem Knoten gefunden wurde und die Distanz sich später nicht mehr ändert.

• Um zu verhindern, dass der Algorithmus bereits verarbeitete Knoten erneut besucht.

Was sind die ersten 5 Knoten die aus der Priority Queue entnommen werden?

• ADEF

• ABFCH

• ABCFH

• ABFEC

Welcher Knoten wird vor E aus der Priorityqueue genommen?

• A

• F

• H

• C

Welcher Laufzeit hat der Algorithmus von Djikstra, wenn er mit einer Prioritätswarteschlange und auf einen stark besetzen Graphen mit nur positiven Kantengewichten ausgeführt?

• O(V²)

• O(V*E)

• O(E*logV)

• O(V*logE)

Welche Laufzeit hat Bellmann-Ford?

• O(V+E)

• O(V*E)

• O(V*logE)

• O(log V *E)

Die Algorithmen starten

immer im markierten Startknoten s. Bei gleichem Abstand werden die Knoten alphabetisch abgearbeitet. Bellman Ford arbeitet immer alphabetisch.
Welcher Algorithmus könnte diese Wege ausgewählt haben?

• Djikstra

• BF

• Beide

• Keiner

Die Algorithmen starten

immer im markierten Startknoten s. Bei gleichem Abstand werden die Knoten alphabetisch abgearbeitet. Bellman Ford arbeitet immer alphabetisch.
Welcher Algorithmus könnte diese Wege ausgewählt haben?

• Djikstra

• BF

• Beide

• Keiner

Welches Argument spricht am stärksten für die Verwendung des Bellman-Ford-Algorithmus gegenüber anderen kürzesten-Pfad-Algorithmen?

• Er bietet eine bessere Zeitkomplexität für dichte Graphen.

• Er kann Graphen mit negativen Kantengewichten korrekt verarbeiten.

• Er ist spezialisiert auf ungerichtete Graphen ohne Zyklen.

• Er benötigt weniger Speicherplatz als Dijkstra's Algorithmus