未分類
秋期
ITパスポート 2010年 秋期 問72
72 / 100
図 1 の A」地点から C。地点へ行くとき, 通過する地点が最も少なくてすむ最短経路 は, 図 2 のように数えることによって 3 通りあることが分かる。A地点から, C。地点 を経由して, D。地点へ行く最短経路は何通りあるか。 Ci 3 a G Ss C oO DO ag ® Ww ん a (2) Q1) ( ) 内数字は, Aiからそ の地点までの最短経路の数 を表す。 図1 図2
正解と解説
表示する
正解 イ
9
最短経路の数は、各地点へ至る経路数を隣接地点からの和で数えます。図によればCまでの経路が3通りあり、そこからD地点まで同様に数えると合計9通りとなり、正解はイです。