Steiner Tree
コードについての説明
最小シュタイナー木のコストを効率よく求めるアルゴリズム.
シュタイナー木とはターミナル点(要求点)の集合を含むような木(もとのグラフの部分グラフ)のことである. このうちコストが最小のものを最小シュタイナー木という.
岩田さんのスライド を参考にさせていただいた.
元論文は "The steiner problem in graphs" [Dreyfus Wagner 1971]
以下の実装では元論文とは異なり, Warshall Floyd を行わず, DP 遷移を Dijkstra 法を用いて更新することでターミナル数 $t$ に関して $\O(n 3^t + (n+m) 2^t \log n )$ の時間計算量で求めている(FPT). グラフは巨大だがターミナル数が小さいという場合にこの改良が効いてくる.
重みなし最小シュタイナー木問題の場合高速メビウス変換を用いて $O^{\ast}(2^t)$ に計算量が落ちるみたい(参考).
(関数)
add_edge$(u, v, cost)$ : 費用が $cost$ の辺 $(u,v)$ を追加する
solve$(terminal)$ : 頂点集合 $terminal$ をターミナル点の集合とするような最小シュタイナー木のコストを返す.
時間計算量: $\O (n 3^t + (n + m) 2^t \log n)$
コード
template<typename T> class SteinerTree {
private:
struct edge {
int to;
T cost;
};
int V;
vector<vector<edge> > G;
vector<vector<T> > dp;
const T inf = numeric_limits<T>::max() / 10;
using pti = pair<T, int>;
public:
SteinerTree(int node_size) : V(node_size), G(V){}
void add_edge(int u, int v, T cost){
G[u].push_back((edge){v, cost}), G[v].push_back((edge){u, cost});
}
T solve(vector<int>& terminal){
int t = (int)terminal.size();
if(t == 0) return (T)0;
dp.resize((1 << t), vector<T>(V, inf));
for(int i = 0; i < t; i++){
dp[(1 << i)][terminal[i]] = 0;
}
for(int i = 1; i < (1 << t); i++){
for(int j = 0; j < V; j++){
for(int k = i; k > 0; k = (k - 1) & i){
dp[i][j] = min(dp[i][j], dp[k][j] + dp[i ^ k][j]);
}
}
if(i == (1 << t) - 1) break;
priority_queue<pti, vector<pti>, greater<pti> > que;
for(int j = 0; j < V; j++){
que.push(make_pair(dp[i][j], j));
}
while(!que.empty()){
pti p = que.top();
que.pop();
int v = p.second;
if(dp[i][v] < p.first) continue;
for(auto& e : G[v]){
if(dp[i][e.to] > dp[i][v] + e.cost){
dp[i][e.to] = dp[i][v] + e.cost;
que.push(make_pair(dp[i][e.to], e.to));
}
}
}
}
return dp[(1 << t) - 1][terminal[0]];
}
};
verify 用の問題
AOJ : Modern Announce Network 提出コード (t = 3 の場合のみ)