Antworten
Der Bellman-Ford-Algorithmus berechnet die kürzesten Pfade von einem einzelnen Quellscheitelpunkt zu allen anderen Scheitelpunkten in einem gewichteten Digraphen. Der Algorithmus überschätzt die Länge des Pfades vom Startscheitelpunkt zu allen anderen Scheitelpunkten und lockert diese Schätzungen iterativ, indem neue Pfade gefunden werden, die kürzer als die zuvor überschätzten Pfade sind. Beim Bellman Ford Algorithmus wird an einem beliebigen Knoten im Graphen gestartet und nach und nach die jeweils günstigste Kante zum nächsten Knoten eingefügt.
Im Prinzip wird jeder mögliche Weg von Punkt zu Punkt ausprobiert. Der kürzeste Weg wird sich gemerkt. Dadurch ergibt sich dann irgendwann ein kürzester Weg.
