Pythonでグラフ内の全頂点ペア間の最小コストの合計を求めるプログラム

問題の概要

n個の頂点とm個の辺からなる重み付きグラフを考えます。各辺の重みは2の冪乗（1、2、4、8など）で与えられ、グラフは連結しているため、任意の頂点から任意の頂点へ移動することが可能です。ある頂点ペア間の移動コストは、その経路上の辺の重みの総和として定義されます。

この記事では、すべての頂点ペア間の最小コストの合計を求めるPythonプログラムを紹介します。

入力例と出力

例として、次のようなグラフが与えられたとします。

頂点数 n = 6 の場合、出力は 2696 となります。つまり、すべての頂点ペア間の最短距離を合計すると2696になるということです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 関数 par_finder() を定義します。引数は i、par です。
  • par[i] が -1 と等しい場合、i を返します
  • res := par_finder(par[i], par)
  • par[i] := res
  • res を返します
• 関数 helper() を定義します。引数は i、par、w、G、n です。
  • child := 1
  • G[i] 内の各要素 item について:
    • item[0] が par と等しい場合は次の反復へ進みます
    • それ以外の場合、child := child + helper(item[0], i, item[1], G, n)
  • par が -1 でない場合、ans := ans + child * (n - child) * (1 * 2^w)
  • child を返します
• G := n+1 個の空リストを含む新しいリストを作成します
• edges := 新しいリストを作成します
• roads の各要素 item について:
  • u := item[0]、v := item[1]、w := item[2]
  • (u-1, v-1, w) を edges の末尾に追加します
• edges を辺の重みを基準にソートします
• par := サイズ n+1 のリストを -1 で初期化して作成します
• r_edge := 新しいリストを作成します
• edges の各要素 i について:
  • par_finder(i[0], par) が par_finder(i[1], par) と等しい場合は次の反復へ進みます
  • それ以外の場合:
    • i を r_edge の末尾に追加します
    • (i[1], i[2]) を G[i[0]] の末尾に追加します
    • (i[0], i[2]) を G[i[1]] の末尾に追加します
    • par[par_finder(i[0], par)] := par_finder(i[1], par) とします
• ans := 0 と初期化します
• helper(0, -1, 0, G, n) を呼び出します
• ans を返します

アルゴリズムのポイント

この解法の核心は次の2点にあります。

• 最小全域木（MST）の構築： 辺の重みが2の冪乗であるという性質により、クラスカル法で最小全域木を構成すると、木上のパスがすべての頂点ペア間の最短経路となります。
• 各辺の寄与の計算： 全域木上の各辺について、その辺を取り除いたときに分かれる2つの部分木のサイズを child と n - child とします。この辺を通る頂点ペアは child × (n - child) 通り存在するため、その辺が合計に寄与する量は child × (n - child) × 2^w となります。

実装例

以下の実装を見ると、理解がより深まるでしょう。

def par_finder(i, par) :
    if par[i] == -1 :
         return i
    res = par_finder(par[i], par)
    par[i] = res
    return res

def helper(i, par, w, G, n) :
    global ans
    child = 1
    for item in G[i] :
        if item[0] == par :
            continue
        else :
            child += helper(item[0],i,item[1], G, n)
    if par != -1 :
        ans += child * (n - child) * (1 << w)
    return child

def solve(n, roads):
    global ans
    G = [[] for i in range(n + 1)]
    edges = []
    for item in roads :
        u,v,w = map(int, item)
        edges.append((u-1, v-1, w))
    edges = sorted(edges,key = lambda item : item[2])
    par = [-1 for i in range(n + 1)]
    r_edge = []
    for i in edges :
        if par_finder(i[0], par) == par_finder(i[1], par) :
            continue
        else :
            r_edge.append(i)
            G[i[0]].append((i[1],i[2]))
            G[i[1]].append((i[0],i[2]))
            par[par_finder(i[0], par)] = par_finder(i[1], par)
    ans = 0      
    helper(0, -1, 0, G, n)
    return ans

print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))

入力

6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]

出力

2696