平成22年度 秋期 ITパスポート試験 問72
テクノロジ／アルゴリズム図 1 の A1 地点から C2 地点へ行くとき，通過する地点が最も少なくてすむ最短経路は，図 2 のように数えることによって 3 通りあることが分かる。A1 地点から，C2 地点を経由して，D4 地点へ行く最短経路は何通りあるか。
出典：平成22年度 秋期 ITパスポート試験 問72
- ア6
- イ9
- ウ12
- エ20
正解：イ
解説
A1 から C2 までは 3 通りです。C2 から D4 へは，右に 2 回，上に 1 回進めばよいので，その並べ方は 3 通りです（上を 1 回どこに入れるかで 3 通り）。経由する場合は掛け算なので 3×3＝9 通りです。
選択肢ごとの解説
- ア誤り。3＋3 のように足した値です。経由する場合は掛け算になります。
- イ正しい。A1 から C2 まで 3 通り，C2 から D4 まで 3 通りで，3×3＝9 通りです。
- ウ誤り。C2 から D4 までの経路数を誤って数えた値です。
- エ誤り。A1 から D4 までの全最短経路（6 通りの組合せ数 C(6,3)＝20）で，C2 を経由する条件が考慮されていません。