Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

平成24年度秋季基本情報午後問8

平成24年度秋季 基本情報技術者試験(FE)の午後問題8は、

  • Warshall-Floyd法(ワーシャルフロイド法)を用いて鉄道駅間の最短距離を求める

問題でした。

鉄道の路線から最短距離を求めるという身近な題材であり、これが発展したものがYahoo!などが提供している「乗換案内」アプリにつながっているのかもしれないと思うと、中々楽しい題材だなと思います。

問題を解くだけではもったいないので、問題文中に示されている図3、図4に値を追加(赤字赤い文字)してシミュレーションしてみました。

f:id:rahaema:20190119110721p:plain

プログラム例(h24a_fe_pm8.c)

実行結果

f:id:rahaema:20190119110721p:plain

駅1から駅3への最短距離

駅2を経由していく路線が最短のようです。

区間を指定 => 1 3
最短距離 = 35

駅6から駅4への最短距離

「駅6 → 駅3 → 駅2 → 駅10 → 駅4」と辿るのが最短のようです。

区間を指定 => 6 4
最短距離 = 50

駅5から駅4への最短距離

「駅5 → 駅1 → 駅2 → 駅10 → 駅4」と辿るのが最短のようです。 駅6へ向かったら遠回りになるようですね。

区間を指定 => 5 4
最短距離 = 50

関連(電車繋がりということで)