bellman-ford, Seitenzahl 1

Der Bellman-Ford-Algorithmus berechnet die kürzesten Wege aus einer Quelle in einem gewichteten Digraphen. Für Graphen mit nur nicht negativen Kantengewichten löst der schnellere Dijkstra-Algorithmus auch das Problem. So wird Bellman-Ford hauptsächlich für Graphen mit negativen Kantengewichten verwendet. Der Algorithmus wurde nach seinen Entwicklern Richard Bellman und Lester Ford, Jr. benannt.

Antwort

Können wir den Bellman-Ford-Algorithmus auf ungerichtete Graphen anwenden?

Ich weiß, dass Bellman-Ford-Algorithmus für gerichtete Graphen funktioniert, aber nur für Info möchte ich wissen, ob es für Ungerichtete Graphen funktioniert? Da mit Ungerichtetem Graphen keine Zyklen erkannt werden können, werden parallele Kant...

09.02.2013, 05:54

Antworten

Kann Dijkstras Single Source Shortest Path Algorithmus einen unendlichen Zyklus in einem Graphen erkennen?

So kam ich zu diesem schönen Problem, das Sie auffordert, ein Programm zu schreiben, das feststellt, ob in einem gerichteten Graph ein negativer unendlicher kürzester Pfad existiert. (Man kann sich auch vorstellen, ob ein "negativer Zyklus" im G...

21.11.2013, 14:05