Minimum Steiner Tree
(graph/minimum_steiner_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 13:32:33+09:00
• Include: #include "graph/minimum_steiner_tree.hpp"

Description

最小 Steiner 木は，グラフ $G$ の頂点集合 $S \subset V$ を含む最小の木である．

最小 Steiner 木問題は NP 困難である．Dreyfus-Wagner のアルゴリズムを用いて $\vert S\vert$ に関する指数時間で解ける．

Operations

• T minimum_steiner_tree(vector<vector<Edge<T>>> G, vector<int> terminals)
  • $G$ の terminals を含む最小 Steiner 木の重みを求める
  • 時間計算量: $O(n3^{k} + (n+m)2^k \log n)\,\text{where}\,k = \vert S\vert$

Reference

• Steiner Tree - My Algorithm
• 指数時間アルゴリズム入門 - slideshare

Verified with

• test/aoj/1040.test.cpp

Code

#pragma once
#include <algorithm>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

template <typename T>
T minimum_steiner_tree(std::vector<std::vector<std::pair<int, T>>>& G,
                       std::vector<int>& terminals) {
    const int n = G.size();
    const int t = terminals.size();
    constexpr T INF = std::numeric_limits<T>::max() / 2;
    using P = std::pair<T, int>;

    std::vector<std::vector<T>> dp(1 << t, std::vector<T>(n, INF));
    for (int i = 0; i < t; ++i) dp[1 << i][terminals[i]] = 0;

    for (int S = 1; S < (1 << t); ++S) {
        for (int i = 0; i < n; ++i) {
            for (int U = S; U > 0; U = (U - 1) & S) {
                dp[S][i] = std::min(dp[S][i], dp[S ^ U][i] + dp[U][i]);
            }
        }
        if (S == (1 << t) - 1) continue;
        std::priority_queue<P, std::vector<P>, std::greater<>> pq;
        for (int i = 0; i < n; ++i) {
            pq.emplace(dp[S][i], i);
        }
        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (dp[S][v] < d) continue;
            for (auto [u, w] : G[v]) {
                if (dp[S][u] > d + w) {
                    dp[S][u] = d + w;
                    pq.emplace(dp[S][u], u);
                }
            }
        }
    }

    return dp.back()[terminals[0]];
}

#line 2 "graph/minimum_steiner_tree.hpp"
#include <algorithm>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

template <typename T>
T minimum_steiner_tree(std::vector<std::vector<std::pair<int, T>>>& G,
                       std::vector<int>& terminals) {
    const int n = G.size();
    const int t = terminals.size();
    constexpr T INF = std::numeric_limits<T>::max() / 2;
    using P = std::pair<T, int>;

    std::vector<std::vector<T>> dp(1 << t, std::vector<T>(n, INF));
    for (int i = 0; i < t; ++i) dp[1 << i][terminals[i]] = 0;

    for (int S = 1; S < (1 << t); ++S) {
        for (int i = 0; i < n; ++i) {
            for (int U = S; U > 0; U = (U - 1) & S) {
                dp[S][i] = std::min(dp[S][i], dp[S ^ U][i] + dp[U][i]);
            }
        }
        if (S == (1 << t) - 1) continue;
        std::priority_queue<P, std::vector<P>, std::greater<>> pq;
        for (int i = 0; i < n; ++i) {
            pq.emplace(dp[S][i], i);
        }
        while (!pq.empty()) {
            auto [d, v] = pq.top();
            pq.pop();
            if (dp[S][v] < d) continue;
            for (auto [u, w] : G[v]) {
                if (dp[S][u] > d + w) {
                    dp[S][u] = d + w;
                    pq.emplace(dp[S][u], u);
                }
            }
        }
    }

    return dp.back()[terminals[0]];
}

Back to top page