ソースsから宛先fまでの有向非巡回グラフで最長のパスを見つける必要があります。正の重みサイクルが存在しない場合でも、正の重みサイクルが存在しないと仮定します。0または負の重みのサイクルは存在します。この場合、誰かが最長のパスを見つけるためのアルゴリズムを提案できますか？可能であれば出典を引用してください。
ありがとう
3170 次
3 に答える
2
エッジの重みを無効にして、最短パス アルゴリズム (Bellman-Ford など) を実行するだけです。
ゼロ重量サイクルが問題になる可能性があります。最短のものを選択して、パスの同点を解消する必要があります (長さではなく、重量ではありません)。これを行う 1 つの方法は、重みをペア (-(元の重み), 1) にし、それらをペアごとに追加し、辞書式順序付けを行うことです。
2 つの頂点間の最長パスも参照してください。
于 2010-10-04T17:21:20.257 に答える
0
DCG を取得した場合、ターゲットに到達する前に永遠にループすることができます。これが「最長パス」になります。その場合、質問は不完全であり、アルゴリズムはおそらく詳細に応じて異なって見えます。
これは宿題のように聞こえます。
于 2010-10-04T15:47:03.933 に答える
0
これが機能するかどうかはわかりません（確認する必要があります）が...次のようなことができます：
しましょうmin = min weight on the graph。
max = max weight on the graph.
すべてのエッジに新しい重みを設定 = wNew(e) = max - (wOld(e)-min).
現在、負のワイトがあり、ウェイトは逆の順序になっています (つまり、以前w(e1)よりも大きかった場合w(e2)は、現在は小さくなっています)。
ここで最短経路を検索するとどうなるでしょうか。
于 2010-10-04T15:52:23.237 に答える