ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

ダイクストラ法のサンプルプログラム公開

少し前に、ダイクストラ法というグラフ理論におけるノード間の最短経路を求めるアルゴリズムを学習しましたので、そのサンプルプログラムを作ってみました。

グラフ理論ってあまり聞かなかったのですが、物と物の繋がりを抽象化したものをグラフとして扱う理論みたいですね。

繋げられている「物」はノードと呼ばれ、繋いでいるものは「エッジ」と呼ばれ、エッジに「コスト」という数値を設定することもあるみたいです。

ダイクストラ法は「コスト」が大きく関わっていて、
あるグラフで全てのエッジが0より大きいコストを持っているさいに、あるノードを出発点として、各ノードへ一番小さいコストで行ける経路を求めるためのアルゴリズムということでした。

どういう仕組みで最短経路が求まるのか、解説しているWebページを見てみて、まあまあ理解できたんですが、

ダイクストラさんは頭いいですね…。
ところで、構造化プログラミングを提唱したのもこの人ですね。





さて、これだけでは記事にするにはものたりないので、ダイクストラ法で最短経路を求めるサンプルプログラムを書きました。

C#で書いています。
今年はC言語を覚えると強く決意したばかりなのに、いきなりC#ですよ。

今後はC言語でサンプルプログラムを書いたほうがいいですね…。


Yahoo!ボックスにて公開しています。

Sample.zip Yahoo!ボックス
http://yahoo.jp/box/8Gxj_V

このプログラムはCUIです。
操作方法は逐一ガイダンスしているので、すぐにわかると思います。


そして、このプログラムにはソースコードを同梱しました。
サンプルプログラムはいつもソースコードを同梱していますね。

ダイクストラ法の実装方法やその他の箇所に、無駄な処理とか、もっとエレガントにできるんじゃないかというところがあれば、コメントを頂きたいのです。

みなさま、ぜひともダウンロードして、ソースを読んで、ご指摘ください。


ところで最近C#では、クラスのコンストラクタで核となる処理をして、あとはそのクラスを処理結果の取得に使うという設計方法を、私、個人的によく使っているのですが、これってどうなんでしょうかね…。

コンストラクタに重い処理をさせるのはあまりよくないのかもしれませんね。

ただ、処理をコンストラクタではなく普通のメソッドにしたとして、処理前に処理結果の取得をリクエストできるような設計はよくないですしね~。

処理するメソッドの戻り値を、処理結果取得用のクラスにするというのもありますが、
そうすると処理するクラスのメンバが処理するメソッドだけになって、「じゃあもうコンストラクタにやらせていいじゃん」というふうになってしまうと思うんですけどね。


話がそれてしまいましたが、とにかくダウンロードお待ちしております!

コメントください!



ところで、今日は文章の書き方がヘタクソですね…。

文章能力って、その時々のコンディションによって大きく左右されている気がします。

tag: グラフ理論 C# サンプルプログラム

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/388-6a0f700e
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。