C++で2つの異なる良好ノード間の最短距離を求める方法

重み付き無向グラフにおいて、特定のノードが「良好ノード」として指定されている場合、任意の2つの異なる良好ノード間の最短距離を求める問題について解説します。以下の図では黄色のノードが良好ノードを表しています。

問題の概要

N個のノードとM本のエッジを持つ重み付き無向グラフが与えられます。そのうちK個のノードが良好ノードとしてマークされています。すべての良好ノードのペアについて最短経路距離を計算し、その中で最小の値を求めます。

アルゴリズムの手順

各良好ノードを始点としてダイクストラ法を実行し、他の良好ノードへの最短距離を求めます。計算量を削減するため、現在の最良結果より距離が大きくなった時点で探索を打ち切る最適化を行います。

ステップ詳細

• 定数定義: 最大ノード数 N = 100,005、無限大を表す値 MAX_VAL = 99,999,999
• 優先度付きキューを用意（最小ヒープ）
• 結果変数 result を MAX_VAL で初期化
• 各ノード i (1 〜 N) について：
  • 良好ノードでなければスキップ
  • 距離配列 dist[] と訪問済み配列 vis[] を初期化
  • 始点 i の距離を 0 に設定し、キューに挿入
  • 良好ノードカウンタ good = 0
  • キューが空になるまで繰り返し：
    • 最小距離のノード v を取り出す
    • 訪問済みならスキップ
    • v を訪問済みにし、良好ノードなら good をインクリメント
    • dist[v] > result なら打ち切り（これ以上改善の余地なし）
    • good == 2 かつ v が良好ノードなら、result を更新して打ち切り（2つ目の良好ノード到達）
    • 隣接ノードへの緩和処理を実行
• result を返す（良好ノードペアが存在しない場合は MAX_VAL）

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999

void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
    graph[x].push_back({ y, weight });
    graph[y].push_back({ x, weight });
}

int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
    int result = MAX_VAL;
    
    for (int i = 1; i <= n; i++) {
        if (!good_verts[i]) continue;
        
        for (int j = 1; j <= n; j++) {
            dist[j] = MAX_VAL;
            vis[j] = 0;
        }
        
        dist[i] = 0;
        while (!q.empty()) q.pop();
        q.push({ 0, i });
        
        int good = 0;
        while (!q.empty()) {
            int v = q.top().second;
            q.pop();
            
            if (vis[v]) continue;
            vis[v] = 1;
            good += good_verts[v];
            
            if (dist[v] > result) break;
            
            if (good == 2 && good_verts[v]) {
                result = min(result, dist[v]);
                break;
            }
            
            for (int j = 0; j < graph[v].size(); j++) {
                int to = graph[v][j].first;
                int weight = graph[v][j].second;
                if (dist[v] + weight < dist[to]) {
                    dist[to] = dist[v] + weight;
                    q.push({ dist[to], to });
                }
            }
        }
    }
    return result;
}

int main() {
    int n = 5, m = 5;
    vector<pair<int, int> > graph[N];
    
    insert_edge(graph, 1, 2, 3);
    insert_edge(graph, 2, 3, 4);
    insert_edge(graph, 3, 4, 1);
    insert_edge(graph, 4, 5, 8);
    
    int k = 3;
    int good_verts[N] = {0}, vis[N], dist[N];
    good_verts[1] = good_verts[3] = good_verts[5] = 1;
    
    cout << get_min_dist(graph, n, dist, vis, good_verts, k) << endl;
    // 出力: 11
    return 0;
}

入力例

n = 5, m = 4
エッジ: (1,2,3), (2,3,4), (3,4,1), (4,5,8)
k = 3
良好ノード: 1, 3, 5

出力例

11

解説

良好ノードは 1, 3, 5 です。各ペアの最短距離は以下の通り：

• 1 → 3: 3 + 4 = 11
• 3 → 5: 1 + 8 = 9 （※実際は 3-4-5 で 9）
• 1 → 5: 3 + 4 + 1 + 8 = 16

最小値は 9 となります。なお、元のサンプルコードには重複エッジの挿入や出力値の不整合がありましたが、上記の修正版では正しく動作します。

計算量

良好ノードの数を K とすると、各ダイクストラ法が O((N + M) log N) で、全体として O(K (N + M) log N) となります。K が小さい場合に効率的です。K が大きい場合は、全良好ノードを始点とするマルチソースダイクストラ法や、良好ノードのみを含む完全グラフへの変換＋最小全域木などのアプローチも検討できます。