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 Grafik funktioniert? Da mit Ungerichtetem Graphen keine Zyklen erkannt werden können, werden parallele Kanten als Cycles !! betrachtet. Bitte klären Sie.Können wir Bellman Ford-Algorithmus auf ungerichtete Graph
In der Tat ist jeder ungerichtete Graph auch ein gerichteter Graph.
Sie müssen nur die Kanten {u, v} zweimal angeben (u, v) und (v, u).
Aber vergessen Sie 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 darf.
Wenn es nicht gut ist, Bellmann-Ford zu verwenden.
Um dies näher auszuführen - da der Graph nur nichtnegative Kanten haben muss, bedeutet das, dass Sie vielleicht stattdessen den Dijkstra-Algorithmus verwenden möchten, da er asymptotisch schneller ist. – templatetypedef
Ich habe die gleichen Zweifel. Danke für die Klarstellung. – whitehat
Schauen Sie sich [this] (http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph) an. – Nik