グラフライブラリに取り組んでいます。ソースノードからターゲットノードに到達する前にトラバースする必要のあるノードの最小数の最大数である、最も離れている2つのノードを見つける機能が必要です。
単純な方法の1つは、各ノードから他のすべてのノードへの分離度を計算し、すべてのノードに対して同じことを繰り返すことです。
これの複雑さはであることがわかりますO(n^2)。
この問題に対するより良い解決策はありますか？
質問する
1607 次
2 に答える
2
Floyd-Warshall アルゴリズムを使用して、すべてのペアの最短経路を見つけます。次に、結果を反復処理して、最長のパスを持つものを見つけます。
于 2013-01-15T10:56:08.377 に答える
0
グラフに仮定がなければ、 Floyd-Warshallが最適です。
グラフがまばらな場合(つまり、ノードごとのエッジが比較的少ない場合、または|E|<<|N|^2)、Johnsonの方が高速である可能性があります。
ユニットエッジの重み（あなたの場合のようです）を使用すると、各ノードの最も遠いノード（ BFSO(|N|.|E|)を使用）を計算することによる単純なアプローチが になります。これはおそらくさらに改善される可能性がありますが、今のところ方法がわかりません。
于 2013-01-15T13:23:14.603 に答える