Pythonでネットワーク全体にメッセージが伝わるまでの時間を求めるプログラム

問題の概要

数値 n とエッジのリストが与えられるとします。0からNまでのラベルが付いたn個の異なるノードがひとつのネットワークを形成しています。各エッジは無向グラフにおける (a, b, t) という形式で表され、これはノードaからb(またはbからa)へメッセージを送信するのに t 時間かかることを意味します。

あるノードがメッセージを受信すると、そのノードは直ちに隣接するノードへメッセージを転送(フラッド)します。すべてのノードが互いに接続されているとき、ノード0から発信されたメッセージがすべてのノードに届くまでにかかる時間を求めるのがこの問題の目的です。

たとえば、入力が以下の場合を考えてみましょう。

• n = 3
• edges = [[0, 1, 3], [1, 2, 4], [2, 3, 2]]

このとき出力は 9 になります。最も遠い位置にあるノード3が「0 → 1 → 2 → 3」という経路でメッセージを受け取り、所要時間が 3 + 4 + 2 = 9 となるためです。

解き方のアプローチ

この問題は、重み付きグラフにおける単一始点最短経路問題として捉えることができ、ダイクストラ法(Dijkstra's algorithm)を使うことで効率的に解けます。ノード0を始点とし、優先度付きキュー(ヒープ)で「累積時間」と「ノード」のペアを管理しながら、各ノードへの最短到達時間を求めていきます。

具体的な手順

まず、グラフを構築するための関数 build_graph() を定義します。

• graph := 空のマップ(辞書)を用意する
• edges 内の各 (src, dest, t) に対して:
  • graph[src] に (dest, t) を追加
  • graph[dest] に (src, t) を追加(無向グラフのため双方向)
• graph を返す

次に、メイン処理で以下を実行します。

• graph := build_graph(edges)
• visited := 新しいセット(訪問済みノード管理用)
• heap := ペア (0, 0) を持つ新しいヒープ
• heap が空でない限り、以下を繰り返す:
  • (current_total_time, node) := ヒープの先頭要素を取り出して削除
  • node を訪問済みとしてマーク
  • 訪問済みノード数が (n + 1) と等しければ、current_total_time を返す
  • graph[node] 内の各ペア (nei, time) について:
    • nei が未訪問であれば、(current_total_time + time, nei) をヒープに挿入

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

import heapq
from collections import defaultdict
class Solution:
   def solve(self, n, edges):
      graph = self.build_graph(edges)  
      visited = set()
      heap = [(0, 0)]
      while heap:
         current_total_time, node = heapq.heappop(heap)
         visited.add(node)  
         if len(visited) == (n + 1):
            return current_total_time
         for nei, time in graph[node]:
            if nei not in visited:
               heapq.heappush(heap, (current_total_time + time, nei))
   def build_graph(self, edges):
      graph = defaultdict(set)
      for src, dest, t in edges:
         graph[src].add((dest, t))
         graph[dest].add((src, t))
      return graph
ob = Solution()
n = 3
edges = [[0, 1, 3],[1, 2, 4],[2, 3, 2]]
print(ob.solve(n, edges))

入力

3, [[0, 1, 3],[1, 2, 4],[2, 3, 2]]

出力

9

計算量について

このアルゴリズムの計算量は、ノード数をV、エッジ数をEとすると O((V + E) log V) になります。ヒープ操作に log V のコストがかかり、各エッジを高々一度ずつ処理するためです。また、空間計算量はグラフの隣接リストとヒープの保存に O(V + E) 必要となります。

まとめ

本記事では、ダイクストラ法とPythonの heapq モジュールを組み合わせて、ネットワーク内の全ノードにメッセージが行き渡るまでの最小時間を求める方法を解説しました。重み付きグラフの最短経路問題は、通信ネットワークや配送ルート最適化など、さまざまな実務シーンで応用される重要なアルゴリズムです。ぜひ自分のコードでも試してみてください。