はじめに
おひさしぶりです。ここ半年は仕事や将来の事で本当に忙しく、twitterすら行う余裕がありませんでしたが、最近はほんの少しだけ余裕が出てきたので約9ヶ月ぶりにQiitaの記事を更新したいと思います。
さて、今回の記事ですが、最短経路を求めるプログラムをC言語で作成したのでそのソースコードを公開したいと思います。最短経路を求める問題は学生時代に自分が所属していた研究室でも行っていましたが、当時はGAやNNで手一杯であり、最短経路は蚊帳の外でした(興味はあったんですけどね)
そんなわけで学生時代に出来なかった最短経路を今から求めていこうと思います。短い記事になると思いますが、よろしくお願いします。
参考資料
いきなりソースコードを紹介してもいいと思いますが、今回は最短経路を求めるプログラムを書く際に参考にした資料から紹介したいと思います。ぶっちゃけて言うとこの資料にソースコードのほとんどが書かれていたので、そのコードをC言語に置き換えたものになっています(苦笑)プログラムの説明も詳しく書いてあるので気になる方は下記のURL先の資料と一緒に見てください。
参考資料(基本情報技術者試験 平成29年春期午後問8 p35-40):
URL:https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_1/2017h29h_fe_pm_qs.pdf
ソースコード
ソースコードは下記のURL先にあるのでご覧ください。
URL:https://gist.github.com/KUKDfhia/ef142e1ce3d230e8dff1ac831dfb1c90
動かしてみる
今回は下記の図にある経路を使って最短経路を求めていこうと思います。参考資料にある図と同じです。
※基本情報技術者試験 平成29年春期午後問8 p35より引用
出発地の地点番号が0、目的地の地点番号を6とする時、最短経路および最短距離は
図2:実行結果①
出発地の地点番号が5、目的地の地点番号を1とする時、最短経路および最短距離は
図3:実行結果②
とまぁ、こんな感じでコンソール上に最短経路と最短距離が表示されます。今回は地点数が少ないので頭の中でも最短経路は求められると思いますが、これが地点数N=20、30……となると難しいところです。地点数と経路の設定はソースコードをいじれば増やす事が出来ますので、興味があればぜひとも試してみてください。ちなみに最短経路に関する問題を卒業研究でやってみたいのであれば
・アルゴリズムの変更(GAやアントコロニー等)
・各アルゴリズムによる最短経路計算時間の比較、検討
・高速化(地点数が1000、10000でもすぐに求められるかどうか)
などをやってみると担当教授の受けがいいかもしれません(笑)
むすび
今回は最短経路を求めるプログラムについて紹介しました。参考資料として基本情報の問題を使いましたが、最近は自習に使える問題が多く出題されていてびっくりしています。自分は基本情報に合格しており、今は応用情報に向けて勉強していますが、仕事しながらなのでモチべが上がらずに困っています。何か短時間でも出来る効率的な勉強法があればぜひとも教えてください。TwitterでもQiitaでも待ってます(>_<)