グラフの平均最短経路長と直径アルゴリズムの時間の複雑さに違いはありますか？

Question

無向グラフ、重み付けされていないグラフでは、平均最短経路長対、グラフの直径を計算するアルゴリズムの複雑さ、すなわち2つの間の最長最短経路を計算するアルゴリズムの時間複雑さに違いがあります頂点？

Answer 1

Wikipediaによれば、グラフの直径を計算するには、まず、すべてのペアの最短経路を見つける必要があります。すべてのペアの最短経路を計算した後、両方のアルゴリズムはO（V^2）計算に縮小され、その複雑さは同じになります。

Answer 2

いいえいいえ、2つの間の時間の複雑さに違いはありません。

2つの頂点間の最長経路は、最短経路algoを微調整することで見つけることができます。

Answer 3

私はこの件について多くの文献を読んでいませんが、2つは同じであると思われます。しかし、矛盾がある場合は、グラフの直径を計算すると漸近的に速くなると言えます。

私のアルゴリズムは、V*(E+V*log(V))で実行されるDijkstraのアルゴリズムを使用して、すべてのペアの最短パスを計算することです。その後、これらの値すべてに対して算術平均を取ることになります。私はあなたがこれをスピードアップできる方法は見ません。

しかし、グラフの直径を計算するために、このプロセスをスピードアップするために使用できる巧妙なトリックがあるかもしれません。しかし、上限として、あなたは単純に全ペアの最短パスを上に取って直径を得ることができます。これは、平均最短パスを計算するのと同じ実行時の複雑さを持ちます。