エッジの重みが負の有向グラフがあります。グラフはプログラムによって変更され、負のサイクルを形成することがあります。その場合、最短経路アルゴリズム (Bellman-ford/Johnson/Floyd-Warshall) は、そのような負のサイクルの存在を検出して失敗しますが、他の有用な情報は生成されません。
どのエッジが負のサイクルを引き起こしているのかを特定し、グラフでそのような変更を禁止したいと考えています。誰かがポインタで私を助けることができますか?
ありがとう、
ポール
1 に答える
0
ポール、エッジ (ソース、宛先、重み) を追加しようとしていて、宛先からソースまでの距離がわかっている場合、新しい重み + 古い距離が負の場合にのみ、負のサイクルが作成されます。
一方、グラフを取得したばかりの場合、ベルマンフォード アルゴリズムは負のサイクルを検出し、負のサイクルが見つかったときにそれを示すことができます。それを行う実装を (単に失敗するのではなく) 見つけるか、自分で作成する必要があります。これは難しいアルゴリズムではなく、ウェブ上にはたくさんの疑似コードがあります。
（特注品をご希望の場合は、おそらく数日間のコンサルティング作業になります。私はこの種のことを生計のために行っており、喜んでお手伝いします。）
何が必要なのか正確にはわかりません。わかりませんが、Bellman-Ford のオンライン バージョンがあり、新しいエッジが追加されたときに距離を安価に最新の状態に保ち、悪いエッジを追加すると悲鳴を上げると思います。
于 2013-09-24T18:41:06.583 に答える