最長経路探索

質問

グラフの最長経路(クリティカルパス)を求めたいのですが、
・閉路無し有向グラフ
・重み付きグラフ（辺ではなくノードの方に重みがある）
・スタートとゴールのノードが各々1つ与えられている
・スタートからどの経路を辿ってもゴールには辿り着く
以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？
幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。
言語はVBAで、そもそも詳しくないのですが、
考え方など教えて頂けないでしょうか。
お願い致します。

回答No.3

Tacosan · ベストアンサー

辺に重みのあるグラフを考えると, その上の最長経路問題は「辺の重みの正負をすべて入れ替えたグラフでの最短経路問題」になりますよね?
で, 得られたグラフには重みが負の辺もあるのでダイクストラ法は使えないんだけど, 閉路を持たないことは仮定されているのでベルマン・フォードを使えば最短経路 (= 元のグラフにおける最長経路) が分かります.

お礼

Tacosanさん、わかりました。
最短経路探索は貪欲法のダイクストラ法しか知らなかったので、失礼しました。
どうもありがとうございます！

回答No.2

Tacosan

ごめん, 間違えた. フローは関係なく, ただの最短経路問題です. うろ覚えで書くと, やっぱりよくないなぁ.
で, #1 のように変換するとダイクストラ法は使えないはずです. というのは, ダイクストラ法は「負の重みの辺が存在しない」ことに依存しているのですが, #1 の変換ではどう考えても負の重みの辺ができてしまいます.
ただし, 今考えているグラフは閉路を持たないことが分かっているので, 最短経路を求めることは可能です. そして, 始点と終点は 1つずつなのでベルマン・フォード (これと混同してた) で最短経路を求めることができます.

お礼

Tacosanさん御回答ありがとうございます。
すみません。ちょっと混乱してしまって。
辺の重みを全て負数に置き換えると、質問の条件では、最長経路問題が最短経路問題に置き換えられ、ベルマン・フォード法が有効ということですか？
最大フロー＝クリティカルパスなのかと思いましたが、そういう訳では。。

回答No.1

Tacosan

「ノードに重みがある」というのは「そのノードに入る辺に重みがある」ように変形することができます. たとえば, ノードa の重みが 3 なら, ノードa に入るすべての辺の重みを 3 とします. スタートノードが 1個だけなら, 必ずそこを通る関係上その重みは無視することができます. スタートノードが複数あるなら, そのようなすべてのノードへの辺を持つ重み 0 のノードを追加すれば OK.
これで「辺に重みのあるグラフ」に変形できるので, そのすべての辺の重みの符号を逆にして最短経路を求める. フルカーソン・フォードでも使うか. これなら最悪ノード数の 3乗に比例する実行時間.

お礼

Tacosanさん御回答ありがとうございます。
>「辺に重みのあるグラフ」に変形できるので, そのすべての辺の重みの符号を逆にして最短経路を求める.
これは、質問の条件内であれば、ダイクストラ法でも求められるということでしょうか？
>フルカーソン・フォードでも使うか.
知らなかったのでググってみました。ありがとうございます。
つまり、自分の質問は、最長経路問題ではなく、最大フロー問題なのですね。
正当性がわからなかったのですが、これでなんとかなりそうです。