Bellman-Ford-Algorithmus Flashcards
Was ist der Vorteil des Bellman-Ford Algorithmus gegenüber dem Dijkstra Algorithmus?
Der Bellman-Ford Algorithmus kann auch bei Graphen mit negativen Kantengewichten angewendet werden.
Nenne die Voraussetzungen des Bellman-Ford Algorithmus.
Gewichteter Digraph (auch neg. Kantengewichte zugelassen)
Was versteht man unter dem Prinzip der optimalen Substruktur?
Ein kürzester Weg zwischen zwei beliebigen Knoten i und j in einem Graphen g(V,E,w) setzt sich immer aus kürzesten Teilwegen zusammen.
(Wichtig! Das Prinzip der optimalen Substruktur gilt nicht bei Graphen mit neg. Zyklen)
Wahr oder falsch?
Das Prinzip der optimalen Substruktur gilt bei allen Graphen.
Falsch!
Das Prinzip der optimalen Substruktur gilt nicht bei Graphen mit neg. Zyklen.
Wo wird das Prinzip der optimalen Substruktur im Bellman-Ford Algorithmus angewendet?
Bei der Bestimmung von uij
Nenne die Abbruchkriterien des Bellman-Ford Algorithmus.
Treten auf der Hauptdiagonalen negative Einträge auf, kann der Algorithmus abgebrochen werden, da die ein Hinweis auf einen negativen Zyklus ist.
Verändern sich die Einträge der U-Matrix von einer Iteration zur Nächsten nicht, so kann der Algorithmus abgebrochen werden, da bereits eine optimale Lösung vorliegt.
Der Algorithmus muss maximal |V|-1 mal durchlaufen werden, danach noch ein weiteres Mal zum Test auf einen negativen Zyklus.
Welcher Algorithmus löst das k-kürzeste Wege Problem?
Yen Algorithmus
Nenne die Abbruchkriterien des Yen-Algorithmus
k = Anzahl gewünschter kürzester Wege K = leere Liste
