ネットワークスペシャリスト 2024年 午前2 問05

ルートAの最短経路木【午前2解説】

正解の理由

解法ステップ

1. 初期化：$d(A)=0$、他は $d=\infty$。前駆ノードは未設定。
2. Aを確定（最短距離0）。隣接更新：
   • $d(B)=1$（前駆 B←A）
   • $d(E)=4$（前駆 E←A）
   • $d(D)=7$（前駆 D←A）
3. 最小未確定はB（$d=1$）。Bを確定、隣接更新：
   • E について $1+2=3<4$ → $d(E)=3$（前駆 E←B）
   • C について $1+4=5$ → $d(C)=5$（前駆 C←B）
4. 次にE（$d=3$）を確定、隣接更新：
   • D について $3+3=6<7$ → $d(D)=6$（前駆 D←E）
   • C について $3+1=4<5$ → $d(C)=4$（前駆 C←E）
5. 次にC（$d=4$）を確定。C→Dの候補は $4+3=7>6$ のため更新なし。
6. 最後にD（$d=6$）を確定。結果として前駆関係は
   • B←A（辺 AB）
   • E←B（辺 BE）
   • C←E（辺 CE）
   • D←E（辺 ED） となり、スパニングツリー（最短経路木）は辺AB, BE, CE, EDを含みます。

選択肢別の誤答解説

• ア: Aと E
  A→Eの直接辺（重み4）は存在しますが、A→B→Eの経路が重み3と短いため、Eの前駆はBになり、ABまたはBEは木に入りますがAEは入らないため誤りです。
• イ: Bと C
  B–C（重み4）は存在しますが、最短経路木でのCの前駆はE（A→B→E→Cの経路重み4）であり、CとBは隣接しません。したがって誤りです。
• ウ: Cと D
  辺C–D（重み3）自体は存在しますが、Dの最短経路はE経由（合計6）であり、C経由だと合計7になるためDの親はEです。よってCとDは隣接しません。
• エ: Dと E
  Dの前駆がE（E→Dの辺が最短経路木に含まれる）であるため、ノードDとEはスパニングツリー上で隣接します。

よくある誤解

• 「スパニングツリー＝最小全域木」と混同する
  スパニングツリーは「木で全頂点をつなぐ」こと一般を指しますが、問題は「Aをルートとする」最短経路木（単一始点最短路木）を問うため、目的関数が異なります。最小全域木（MST）は全辺の総和を最小にする木であり、アルゴリズムや結果が異なります（Prim/Kruskal vs Dijkstra）。
• 「辺の重みが小さい方が必ず選ばれる」との誤認
  個々の辺の重みではなく、ルートからの経路合計（最短距離）が基準です。局所的に小さい辺があっても、ルートからの合計が大きければ最短経路木には入らないことがあります。
• 同距離の扱いに注意
  複数経路で同じ最短距離になる場合、前駆の選び方（アルゴリズム実装や優先度の扱い）で最短経路木は一意にならないことがあります。本問ではDの経路はE経由が一意に短いため影響しません。

補足コラム

• アルゴリズム対応表
  • 最短経路木（単一始点）：ダイクストラ法（非負重み）やベルマン–フォード（負辺あり）
  • 最小全域木（MST）：Prim法、Kruskal法
• 今回のグラフで使われた「前駆ノード」の概念
  最短経路木は各ノードに「そのノードへ至る最短経路の直前のノード（前駆）」を割り当てることで表現できます。最終的な木はこれら前駆ノードの集合（親子辺）で得られます。
• 実装例（ダイクストラで前駆を出力）

import heapq

G = {
    'A': [('B',1),('E',4),('D',7)],
    'B': [('A',1),('E',2),('C',4)],
    'C': [('B',4),('E',1),('D',3)],
    'D': [('A',7),('E',3),('C',3)],
    'E': [('A',4),('B',2),('C',1),('D',3)],
}

def dijkstra(start):
    dist = {v: float('inf') for v in G}
    prev = {v: None for v in G}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d,u = heapq.heappop(pq)
        if d>dist[u]: continue
        for v,w in G[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, prev

dist, prev = dijkstra('A')
print(dist)  # {'A':0,'B':1,'C':4,'D':6,'E':3}
print(prev)  # {'A':None,'B':'A','C':'E','D':'E','E':'B'}

FAQ