ダイクストラ法はグラフ上のある地点を始点とする最短経路を求めるためのアルゴリズムです。ここでは左上のマスから右下のマスへ移動するために通らなければならないマスの数字の最小値を求めます。

赤は現在調査中の部分。移動できる隣のマスを記憶しておき、そのマスに移動するためのコストの総和をいったん記憶しておきます(黄色の部分)。別ルートでそれよりも小さなコストで移動できる場合はそのマスの値を更新します(緑の部分)。最終的に右下のマスに入っている値が求めるべきコストとなります。

CellsControlクラスを作成する

Labelを縦横6つ並べたものをはりつけたユーザーコントロールを作成します。SetValueメソッドで値を表示させ、SetColorメソッドで背景色を変更します。

SetValuesメソッドは配列で渡せば一気にラベルに表示される文字列を変更できるようにするためのものです。ClearValuesメソッドはすべてのラベルに表示される文字列をクリアし、背景色をもとに戻すためのものです。GetOldBackColorメソッドは最初にバックアップしておいたLabelの背景色を取得します。

Cellクラスの作成

マスが存在する行と列を指定すればその部分の値、そこに到達するまでのコスト、そのマスにはどのマスから来たのかがわかるようにCellクラスをつくります。

Form1クラス

Form1に上記で作成したCellsControlをふたつはりつけます。上が問題で下が経路探索の結果と処理中の状態を表示するためのコントロールです。

アプリケーションが起動したら二次元配列を作成してその値からCellオブジェクトの二次元配列を作成します。同時にCellsControl.SetValuesメソッドでこの値をセットします。

Startボタンがクリックされたら処理を開始します。

2回目以降のテストができるようにします。Shuffleボタンをクリックしたら乱数(0~9までの整数)が生成されCellにセットされます。