6

すべての頂点の重みが 0 以上の有向非巡回グラフがあります。グラフの「開始」である頂点と、グラフの「終了」である別の頂点があります。アイデアは、頂点の重みの合計がより大きくなる始点から終点までのパスを見つけることです。たとえば、次のグラフがあります。

I(0) -> V1(3) -> F(0)
I(0) -> V1(3) -> V2(1) -> F(0)
I(0) -> V3(0.5) -> V2(1) -> F(0)

最もコストのかかるパスは I(0) -> V1(3) -> V2(1) -> F(0) で、コストは 4 です。

現在、上記の例のように、BFS を使用して I から F までのすべてのパスを列挙し、合計が最大のものを選択しています。残念ながら、この方法は本当にナイーブかもしれません。

これを行うためのより良いアルゴリズムはありますか? この問題を別の問題に還元できますか?

4

3 に答える 3

1

一般に、最長経路の問題は NP 困難ですが、グラフは DAG であるため、最初に重みを否定してから最短経路を実行することで解決できます。ここを参照してください。

ウェイトは頂点に存在するため、計算する前に、ウェイトを頂点のエッジに移動することをお勧めします。

于 2013-06-14T13:49:55.010 に答える