16

グラフがあり、その直径 (2 つのノード間の最大距離) を見つける必要がある場合、O(log v * (v + e))複雑な方法でそれを行うにはどうすればよいでしょうか。

Dijkstra's algorithmウィキペディアによると、 を使用してこれを行うことができますbinary heap。しかし、これがどのように機能するのかわかりません。誰か説明してくれませんか？

または疑似コードを表示しますか？

4

10 に答える 10

10

一般的なグラフの場合、直径を計算するための既知の時間計算量アルゴリズムG=(V,E)はありません。O(log V * (V + E))現在の最良の解決策はO(V*V*V)、たとえば、フロイド ウォーシャルのアルゴリズムを使用してすべての最短パスを計算することです。まばらなグラフの場合、つまり がEの場合o(N*N)、ジョンソンのアルゴリズムはO(V*V*log(V)+V*E)より良い時間計算量を提供します。

グラフに非循環 (ツリー) などの特定のプロパティがある場合は、より良くすることができます。

悪いニュースは、ダイクストラは一般的なケースでは十分ではないということです...

于 2013-03-27T08:26:47.620 に答える
1

eci が述べたように、解決策の 1 つは Floyd-Warshall アルゴリズムを使用することです。コードが必要な場合は、C++ バージョンをここで見つけることができます。

于 2014-04-16T05:42:39.133 に答える
1

グラフが重み付けされていないと仮定すると、次の手順で O(V * ( V + E )) の解を見つけることができます。ここで、V は頂点の数、E はエッジの数です。

2 つの頂点 u, v 間の距離を u と v の間の最短経路の長さと定義しましょう。これを d(u, v) で表します。頂点 v の離心率を e(v) = max {d(u, v) | u ∈ V(G)} (V(G) はグラフ G の頂点の集合) を定義します。Diameter(G) = max{e(v) | v ∈ V(G)}

次にアルゴリズムに進みます。

1- V(G) の各頂点 v に対して BFS(v) を実行し、各頂点から他の頂点までの距離の 2 次元配列を作成します。(各頂点から他の頂点までの距離の計算は、BFS アルゴリズムで簡単に実行できます)

2- ステップ 1 で作成された 2 次元配列から各頂点の e(v) を計算します。 3- ステップ 2 から最大 e(v) を見つけて、直径(G) を計算します。

このアルゴリズムを分析すると、O (V * (V + E)) の最初のステップによって支配されていることが簡単にわかります。

ウィキペディアで直径に関するこの部分を読む

線形時間 O(V + E) で実行される別のアルゴリズム 1- 任意のランダムな頂点 v ∈ V(G) で BFS を実行します 2- 最大距離の頂点 u を選択します 3- その頂点 u で BFS を再度実行します 4- 直径はステップ 3 から生成される最大距離

于 2015-11-06T05:44:47.433 に答える
0

最初に、グラフの凸包を見つける必要があります(これは O(nh) であり、h は包のノード数です)。直径の点は凸包上にあるため、問題は h 点で最も遠い点を見つけることになります。したがって、合計順序は O(nh+h*h) になります。

于 2013-05-18T10:34:31.707 に答える
-1

これは、重み付けされていないグラフでのみ発生します。bfs は o(v+e) の最短パス ツリーを提供し、v ソースに対して同じことを繰り返します。

于 2014-07-17T15:12:31.387 に答える