加重無向グラフの合計ペアワイズコスト

Question

任意の2つの頂点に対して、それらを接続する一意のパスが存在する、重み付け無向グラフがあるとします。 nの頂点とn - 1のエッジがあり、各道路のコストはc_iです。

ここで、与えられた2つの頂点を結ぶすべてのパスが通過する道路に依存する特定のコストを持つ場合、どのようにしてすべての都市ペア間の総コストを効率的に計算できますか？

たとえば、各パスのコストは、通過する最初の道路と最後の道路の合計、または通過する各道路のコストのいくつかの合計、またはコストは、それが通過する道路のコストの最小値からマイナスします。道路のコストに依存する数式。

問題を効率的に解決するためにどのようなアルゴリズムを使用しますか？

Answer 1

Choose arbitrary r 
Calculate size(u) for all nodes 
sum = 0 
for each edge (u,v) do: 
    sum = sum + (cost(u,v) * (size(v) * (n-size(v)))) 
return sum 

、max(p)とmin(p)、それが通過する道路の最大値と最小コストを表すものとします。その後sum for all path p max(p)は、あなたがエッジeを挿入

Let G=(V,E) be the input graph, which should be a tree 
Create a graph G' with vertices set V and no edges 
Insert every edge in E to G' from lowest cost to hightest cost 

毎回、以下の方法により求めることができるTotal_cost = sum for all path p [max(p) - min(p)]

その後、それは二つの成分S, Tを接続すると、あなたはSからTにすべてのパスpのためにそれを見ることができます、max(p) = cost(e) sum for all path p max(p)を合計すると見つかります。 2つのコンポーネントを効率的に接続するには、Kruskalのアルゴリズムのアイデアを使用できると思います。

同様に、sum for all path p min(p)と最後に総費用を見つけることができます。

Answer 2

グラフ内の各辺には、{u,v}があります。これを削除すると、2つの接続されていないコンポーネントが得られます。UとVとなります。

このことは、エッジ{u,v}は、元のグラフでV内の各ノードにU内の各ノードから往路の一部であり、|U| * |V|ような経路が存在します。
これは、これらのセットのサイズを計算するために問題が発生することを意味します。

これを行う方法の1つは、任意の頂点rを選択し、すべてのエッジを方向付けることによって "根元にする"ことです。形式はです。あなたがそれをした後、あなたは自分自身にルート付きの指示木を持っています。

線形時間に一度ツリーを横断することにより、あなたは今、各サブツリーのサイズを見つけることができます：あなたは、各有向エッジ(u,v)のために、元のサイズのすべてのサブツリーの大きさを計算した後

size(u) = sum { size(v} | v is a child of u} + 1 

は、 |V|と|U|はsize(v)とn-size(v)です。

次の手順を実行すると、次の高レベル疑似コードを使用して線形時間が算出されます。任意のパスpについて