こんにちは、加重無向グラフで 2 つのノード間の平均距離を計算する方法を理解しようとしています。さらに、このグラフはツリーなので、V - 1 個のエッジがあります。
Floyd Warshall を使用してすべての最短経路を計算し、平均を計算することを考えました。しかし、それは O(E^3) 時間の複雑さになります。そして、それは本当に十分ではありません。
私はそれを解決するために動的プログラミングを使用することも考えていましたが、実際にはどのように見ることができません...誰か私にいくつかの指針を教えてもらえますか? 直接的な答えは望んでいません。それについて考え続けることができるように、いくつかのヒントが必要です:)