Bellman fordアルゴリズムをUndirected Graphに適用できますか？

Question

Bellman-Fordアルゴリズムは有向グラフでは動作しますが、Infoに対してはUn-directedグラフで動作するかどうかを知りたいと思いますか？ Un-directedグラフの場合、平行なエッジはCyclesとみなされるため、サイクルを検出することはできません。どうか明らかにしてください。

Answer 1

実際、すべての無向グラフも有向グラフです。

エッジ{u、v}を2回（u、v）と（v、u）で指定するだけで済みます。

しかし、負の重みを持つエッジもループとしてカウントされることを意味します。 Bellman-Fordアルゴリズムは、負の重みを持つサイクルを含まないグラフ上でのみ動作します。これは、実際には、無向グラフに負の重みを持つエッジが含まれてはならないことを意味します。

Bellmann-Fordを使用するのはかなりうまくいかない場合。