応用情報技術者 2014年秋期午前2 問05

問題文

グラフに示される頂点

V_{1}

から

V_{4}, V_{5}, V_{6}

の各点への最短所要時間を求め、短い順に並べたものはどれか。ここで、グラフ中の数値は各区間の所要時間を表すものとし最短所要時間が同一の場合には添字の小さい順に並べるものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：

V_{4}, V_{5}, V_{6}

イ：

V_{4}, V_{6}, V_{5}

（正解）

ウ：

V_{5}, V_{4}, V_{6}

エ：

V_{5}, V_{6}, V_{4}

🔒 解説は解答すると表示されます

単一始点の最短経路【午前2解説】

正解の理由

出発点

V_{1}

から各頂点への最短所要時間をダイクストラ法で求めると、

V_{4} = 3, V_{6} = 4, V_{5} = 5

となり、短い順に並べると

V_{4}, V_{6}, V_{5}

です。したがって選択肢はイが正しいです。
具体的には、最短路の一例として

$V_{4}$ : $V_{1} \to V_{3} \to V_{2} \to V_{4}$ （ $1 + 1 + 1 = 3$ ）
$V_{6}$ : $V_{1} \to V_{3} \to V_{2} \to V_{4} \to V_{6}$ （ $1 + 1 + 1 + 1 = 4$ ）
$V_{5}$ : $V_{1} \to V_{3} \to V_{2} \to V_{4} \to V_{5}$ （ $1 + 1 + 1 + 2 = 5$ ）
となります。これらが他の経路より短いため、イが妥当です。

解法ステップ

初期化： $d (V_{1}) = 0$ 、他は無限大とする。
未確定頂点の中で最小距離の頂点を選び確定する（ダイクストラの主手順）。
その頂点から伸びる辺で隣接頂点の距離を緩和（改善）する。
全頂点が確定されるまで2-3を繰り返す。
具体的な更新過程（要点のみ）：

初期： $d (V_{1}) = 0$ 、 $d (V_{2}) = 4$ 、 $d (V_{3}) = 1$ 、他は∞
$V_{3}$ (1) を確定 → $V_{2}$ が $1 + 1 = 2$ に更新、 $V_{4}$ は $1 + 4 = 5$ 、 $V_{5}$ は $1 + 5 = 6$
$V_{2}$ (2) を確定 → $V_{4}$ が $2 + 1 = 3$ に更新、 $V_{5}$ は $2 + 4 = 6$ （変わらず）
$V_{4}$ (3) を確定 → $V_{5}$ が $3 + 2 = 5$ 、 $V_{6}$ が $3 + 1 = 4$
残りを確定して終了結果： $d (V_{4}) = 3, d (V_{6}) = 4, d (V_{5}) = 5$ 。

（同一距離の並べ方は問題の規定通り添字の小さい順だが、本問では全て異なるため影響なし）

選択肢別の誤答解説

ア: $V_{4}, V_{5}, V_{6}$
誤り。 $V_{6}$ の最短所要時間は $4$ で $V_{5}$ の $5$ より短く、 $V_{5}$ と $V_{6}$ の順序が逆になっている。
イ: $V_{4}, V_{6}, V_{5}$
正解。上記のダイクストラ手順で得られる距離に一致する。
ウ: $V_{5}, V_{4}, V_{6}$
誤り。 $V_{5}$ を最短とする根拠がない（ $V_{4}$ がより短い）。 $V_{4} = 3 < V_{5} = 5$ である。
エ: $V_{5}, V_{6}, V_{4}$
誤り。 $V_{4}$ を最後に置いているが、 $V_{4}$ が最短（ $3$ ）であるため完全に逆順である。

よくある誤解

直接辺の重みだけで比較してしまう：例えば $V_{1} \to V_{2}$ の重み $4$ を見て $V_{2}$ 経由を過小評価する誤り。中継を使うと合計が小さくなる場合がある（本問では $V_{1} \to V 3 \to V 2$ が $2$ ）。
経路の全パターンを検討しない：近接する選択肢（例： $V_{1} \to V 2 \to V 4$ と $V_{1} \to V 3 \to V 2 \to V 4$ ）を比較せずに短絡的に決めてしまうミス。
同一距離の並べ替えルールを忘れる：等しい場合は添字の小さい順に並べるという条件を見落とすと誤答になる。

補足コラム

ダイクストラ法は非負の辺重みに対して単一始点最短路を効率的に求めるアルゴリズムです。本問のように小さなグラフでは手作業で各ステップを追えば確実に答えが出ます。大規模グラフでは優先度付きキューを用いると時間計算量が改善されます（

O ((V + E) lo g V)

程度）。

簡単な検算用の Python による実装例（確認用）：

import heapq

edges = {
    'V1': [('V2',4),('V3',1)],
    'V2': [('V1',4),('V3',1),('V4',1),('V5',4)],
    'V3': [('V1',1),('V2',1),('V4',4),('V5',5)],
    'V4': [('V2',1),('V3',4),('V5',2),('V6',1)],
    'V5': [('V3',5),('V2',4),('V4',2),('V6',2)],
    'V6': [('V4',1),('V5',2)],
}

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

print(dijkstra('V1'))  # 確認: V4=3, V6=4, V5=5

FAQ

Q. なぜ

V_{4}

が

3

になるのですか？
A.

V_{1} \to V_{3}

が

1

、

V_{3} \to V_{2}

が

1

、

V_{2} \to V_{4}

が

1

で合計

3

となり、他の経路（直接

V_{1} \to V_{2} \to V_{4}

は

4 + 1 = 5

、

V_{1} \to V_{3} \to V_{4}

は

1 + 4 = 5

）より短いためです。

Q. 負の重みがあったらどうする？
A. ダイクストラ法は非負辺重みが前提です。負の重みがある場合はベルマン・フォード法など負辺を扱えるアルゴリズムを使います。

Q. 同一距離があったら並べ替えはどうする？
A. 問題文の規定に従い、最短所要時間が同一の場合は添字（番号）の小さい順に並べます。本問では該当しません。

関連キーワード: 最短経路、ダイクストラ法、グラフ理論、経路探索、辺重み、緩和操作

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

応用情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！