ネットワークスペシャリスト 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