0

ノードと加重エッジを持つ特定のグラフ用に作成した隣接リストがあります。グラフ内で最長のパスを見つけるための最良の方法を見つけようとしています。トポロジカル ソート メソッドがありますが、これは便利だと聞いていますが、最長パスを見つけるためにそれを実装する方法がわかりません。それで、トポロジソートを使用してこれを達成する方法はありますか、それともより効率的な方法がありますか?

以下は、adj リストの出力の例です (括弧内の値は、矢印の後のノードに到達するためのコスト(cost)to get to -> nodeです。

Node 0 (4)->1(9)->2
Node 1 (10)->3
Node 2 (8)->3
Node 3
Node 4 (3)->8(3)->7
Node 5 (2)->8(4)->7(2)->0
Node 6 (2)->7(1)->0
Node 7 (5)->9(6)->1(4)->2
Node 8 (6)->9(5)->1
Node 9 (7)->3
Node 10 (12)->4(11)->5(1)->6
4

2 に答える 2

1

グラフにサイクルがないと仮定すると、そうでない場合、最長パスはあいまいな概念になり、実際にトポロジカルソートを行うことができます。これで、このトポロジー ソートをたどることができます。各ノードについて、すべての先行ノードを調べてソース ノードからの最長距離を計算し、それらに接続するエッジの重みをそれらの距離に追加します。次に、このノードの距離が最も長い先行ノードを選択します。トポロジカル ソートは、すべての前任者の距離が既に正しく決定されていることを保証します。

最長パスの長さに加えて、パス自体も必要な場合。次に、最長の長さを示したノードから開始し、そのすべての先行ノードを調べて、この長さになったノードを見つけます。次に、グラフのソース ノードが見つかるまで、このプロセスを繰り返します。

于 2013-04-30T00:22:44.660 に答える