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 Kanten als Cycles !! betrachtet. Bitte klären Sie.
In der Tat ist jeder ungerichtete Graph auch ein gerichteter Graph.
Sie müssen nur die Kanten {u, v} zweimal (u, v) und (v, u) angeben.
Aber vergiss nicht, dass dies auch bedeutet, dass jede Kante mit einem negativen Gewicht als eine Schleife zählt. Da der Bellman-Ford-Algorithmus NUR auf Graphen arbeitet, die keine Zyklen mit negativen Gewichten enthalten, bedeutet dies, dass Ihr nicht gerichteter Graph keine Kanten mit negativem Gewicht enthalten sollte.
Wenn es nicht gut ist, Bellmann-Ford zu benutzen.
Tags und Links algorithm graph-algorithm data-structures graph bellman-ford