変更ダイクストラのアルゴリズム

Question

エッジ重みWが0と1の有向グラフが与えられます。ソースノードからターゲットノードまでのパスのコストは、ソースノードからターゲットノードまでのパス上にあるエッジの重みの積です。私は多項式時間または他のヒューリスティックを使って最小コスト経路を見つけることができるアルゴリズムを知りたがっていました。

私は、エッジの重み（mod値を取る）のログ値を取って、このグラフにdijkstraを適用すると考えましたが、計算できない精度問題があると思いました。

他の方法がありますか、ログアプローチを改善できますか？

Answer 1

Dijkstraのアルゴリズムでは、ノードにアクセスすると、このノードに至る道がないことがわかります。これは、あなたがより小さい数を得るより多くの頂点を訪問するかのように、0..1の間の重みで辺を掛けるなら、真ではありません。

これは基本的にグラフ内で最も長いパスを見つけることと同じです。これは、0と1の間の数の対数が負であるため、対数をとるという考えを使用することによっても見ることができます。ウェイトの対数の絶対値をとると、最長のパスは乗法グラフの最短パスに対応します。

グラフが非周期的である場合は、直接アルゴリズム（Longest path problemから変更）があります。

1. DAGのトポロジカルな順序を見つける。
2. 各頂点に対して、パスのコストを格納する必要があります。これを最初に1に初期化します。
3. スタート頂点からトポロジカルな順序でDAGを移動します。各頂点ですべての子をチェックし、コストが以前よりも小さい場合はそれを更新します。最も低いコストでこの頂点に到達する頂点も格納します。

最終的な頂点に到達したら、保存された頂点を使用して終了頂点から戻って "最短"パスを見つけることができます。

もちろん、グラフが非周期的でない場合は、ループを無限に繰り返すことでいつでもゼロの最終コストに達することができます。