4

単一のソースからすべての最終目的地までの最長パスを見つけるにはどうすればよいですか。つまり、ソース i1 の場合、i1 -> o1 と i1 -> o2 の間の最長パスを指定します。

代替テキスト

上記のグラフで説明されている凡例は次のとおりです。 (i1、i2) は開始ノード (o1、o2) は終了ノード (1-8) はサブグラフです エッジは +ive/-ive の重みを持つ場合があります

このネットワークの最長パスは、次の順序になっています。

最悪のパス: i1 -> 1 -> 4 -> o1

次に、すべてのパス i1 … -> … o1

その後、i1 -> 5 -> 6 -> o2

(i1 -> 3) または (3 -> 4) サブネットワークの選択が i1 -> 5 より長い場合でも無視する方法が必要

4

2 に答える 2

0

以下は、目的地に到達するための最大のステップ数を提供すると思います（実際のパスではなく、ステップ数のみ）。これはエッジの重みを考慮していません。これsrcは、宛先ノード以外にネイバーがなくなるまでノードを結合することによって機能します。

longestPath (src, dest) =
    if (neighbors(src) == [dest]) then 1
    else 1 + longestPath(newNode(concat (map neighbors (neighbors src))), dest)
于 2012-02-05T16:02:52.413 に答える