21

Bellman-Ford Algorithm が有向グラフで機能することは知っています。無向グラフで機能しますか？無向グラフでは、並列エッジがサイクルと見なされるため、サイクルを検出できないようです。これは本当ですか？アルゴリズムを適用できますか?

4

2 に答える 2

55

実際のところ、無向グラフは有向グラフでもあります。

任意のエッジ {u, v} を (u, v) と (v, u) の 2 回指定するだけです。

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

うまくいかない場合は、Bellmann-Ford を使用しても問題ありません。

于 2013-02-11T00:59:27.047 に答える