ダイクストラ法はグラフ上のある地点を始点とする最短経路を求めるためのアルゴリズムです。ここでは左上のマスから右下のマスへ移動するために通らなければならないマスの数字の最小値を求めます。
赤は現在調査中の部分。移動できる隣のマスを記憶しておき、そのマスに移動するためのコストの総和をいったん記憶しておきます（黄色の部分）。別ルートでそれよりも小さなコストで移動できる場合はそのマスの値を更新します（緑の部分）。最終的に右下のマスに入っている値が求めるべきコストとなります。
CellsControlクラスを作成する
Labelを縦横6つ並べたものをはりつけたユーザーコントロールを作成します。SetValueメソッドで値を表示させ、SetColorメソッドで背景色を変更します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
public partial class CellsControl : UserControl { Label[,] Labels = new Label[6, 6]; Color LabelBackColor; public CellsControl() { InitializeComponent(); // 背景色をもとに戻せるようにバックアップしておく LabelBackColor = label00.BackColor; // 行番号と列番号を指定すればプロパティを変更できるように二次元配列に格納しておく Labels[0, 0] = label00; Labels[0, 1] = label01; Labels[0, 2] = label02; Labels[0, 3] = label03; Labels[0, 4] = label04; Labels[0, 5] = label05; Labels[1, 0] = label10; Labels[1, 1] = label11; Labels[1, 2] = label12; Labels[1, 3] = label13; Labels[1, 4] = label14; Labels[1, 5] = label15; Labels[2, 0] = label20; Labels[2, 1] = label21; Labels[2, 2] = label22; Labels[2, 3] = label23; Labels[2, 4] = label24; Labels[2, 5] = label25; Labels[3, 0] = label30; Labels[3, 1] = label31; Labels[3, 2] = label32; Labels[3, 3] = label33; Labels[3, 4] = label34; Labels[3, 5] = label35; Labels[4, 0] = label40; Labels[4, 1] = label41; Labels[4, 2] = label42; Labels[4, 3] = label43; Labels[4, 4] = label44; Labels[4, 5] = label45; Labels[5, 0] = label50; Labels[5, 1] = label51; Labels[5, 2] = label52; Labels[5, 3] = label53; Labels[5, 4] = label54; Labels[5, 5] = label55; } public void SetValue(int row, int col, int value) { Labels[row, col].Text = value.ToString(); } public void SetColor(int row, int col, Color color) { if(color != Color.Empty) Labels[row, col].BackColor = color; else Labels[row, col].BackColor = LabelBackColor; } } |
SetValuesメソッドは配列で渡せば一気にラベルに表示される文字列を変更できるようにするためのものです。ClearValuesメソッドはすべてのラベルに表示される文字列をクリアし、背景色をもとに戻すためのものです。GetOldBackColorメソッドは最初にバックアップしておいたLabelの背景色を取得します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
public partial class CellsControl : UserControl { public void SetValues(int[,] values) { for (int row = 0; row < 6; row++) { for (int col = 0; col < 6; col++) Labels[row, col].Text = values[row, col].ToString(); } } public void ClearValues() { for (int row = 0; row < 6; row++) { for (int col = 0; col < 6; col++) { Labels[row, col].Text = ""; Labels[row, col].BackColor = LabelBackColor; } } } public Color GetOldBackColor() { return LabelBackColor; } } |
Cellクラスの作成
マスが存在する行と列を指定すればその部分の値、そこに到達するまでのコスト、そのマスにはどのマスから来たのかがわかるようにCellクラスをつくります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
public class Cell { public Cell(int row, int col, int value) { Row = row; Col = col; Value = value; Cost = -1; } public int Row { get; } public int Col { get; } public int Value { get; } public int Cost { set; get; } public Cell From { set; get; } } |
Form1クラス
Form1に上記で作成したCellsControlをふたつはりつけます。上が問題で下が経路探索の結果と処理中の状態を表示するためのコントロールです。
アプリケーションが起動したら二次元配列を作成してその値からCellオブジェクトの二次元配列を作成します。同時にCellsControl.SetValuesメソッドでこの値をセットします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
public partial class Form1 : Form { public Form1() { InitializeComponent(); Init(); } Cell[,] Cells; int MaxRow = 6; int MaxCol = 6; void Init() { int[,] map = { { 0, 1, 9, 1, 1, 1, }, { 9, 1, 6, 1, 1, 1, }, { 3, 1, 9, 1, 3, 1, }, { 0, 1, 1, 1, 1, 1, }, { 9, 9, 9, 9, 9, 1, }, { 3, 9, 7, 9, 3, 1, }, }; CellsControl1.SetValues(map); CellsControl2.ClearValues(); Cells = new Cell[MaxRow, MaxCol]; for (int row = 0; row < MaxRow; row++) { for (int col = 0; col < MaxCol; col++) Cells[row, col] = new Cell(row, col, map[row, col]); } } } |
Startボタンがクリックされたら処理を開始します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
public partial class Form1 : Form { async private void button1_Click(object sender, EventArgs e) { // 経路探索をするにあたってスタート地点は左上、ゴールは右下である int startRow = 0; int startCol = 0; int goalRow = MaxRow - 1; int goalCol = MaxCol - 1; // ひとつひとつの処理を止めて表示する intervalはTask.Delayメソッドにわたす値（ミリ秒） int interval = (int)numericUpDown1.Value; // 前回算出したコストがCellに格納されているのでここでリセットする for (int row = 0; row < MaxRow; row++) { for (int col = 0; col < MaxCol; col++) Cells[row, col].Cost = -1; } // 経路探索の結果を表示する部分をクリアする CellsControl2.ClearValues(); // 次に探索するマスを格納するQueue // これが空になるまで処理は続けられる Queue<Cell> nexts = new Queue<Cell>(); // スタート地点の値をセットし、表示色も変更する Cell start = Cells[startRow, startCol]; start.Cost = start.Value; CellsControl2.SetColor(startRow, startCol, Color.Yellow); CellsControl2.SetValue(startRow, startCol, start.Value); nexts.Enqueue(start); await Task.Delay(interval); while (true) { Cell curPosition = nexts.Dequeue(); // Queue から取り出したCellに相当する部分の背景色を赤に変更する CellsControl2.SetColor(curPosition.Row, curPosition.Col, Color.Red); await Task.Delay(interval); int[] dx = { 1, -1, 0, 0, }; int[] dy = { 0, 0, 1, -1, }; for (int i = 0; i < 4; i++) { int newRow = curPosition.Row + dy[i]; int newCol = curPosition.Col + dx[i]; // 移動不能 if (newRow < 0 || newCol < 0 || newRow >= MaxRow || newCol >= MaxCol) continue; int cost = Cells[curPosition.Row, curPosition.Col].Cost + Cells[newRow, newCol].Value; if (Cells[newRow, newCol].Cost == -1 || Cells[newRow, newCol].Cost > cost) { bool isNew = Cells[newRow, newCol].Cost == -1; Cells[newRow, newCol].Cost = cost; nexts.Enqueue(Cells[newRow, newCol]); // どこから来たのかも必要であれば保存しておく Cells[newRow, newCol].From = Cells[curPosition.Row, curPosition.Col]; // Queueに格納したCellに相当する部分の背景色を変更する // 値が更新されたときはLime、最初の場合はYellowとする if (isNew) CellsControl2.SetColor(newRow, newCol, Color.Yellow); else CellsControl2.SetColor(newRow, newCol, Color.Lime); // そのマスにたどり着くための現段階における最小コストを表示させる CellsControl2.SetValue(newRow, newCol, cost); await Task.Delay(interval); } } // 処理がおわったCellに相当する部分の背景色をもとに戻す CellsControl2.SetColor(curPosition.Row, curPosition.Col, Color.Empty); // Queue が空になったら終了 if (nexts.Count == 0) break; } // コストを最小にするためにとおる部分を赤で表示する int lastRow = goalRow; int lastCol = goalCol; CellsControl2.SetColor(lastRow, lastCol, Color.Red); // ゴールからスタート位置にむけて処理をおこなう while (true) { if (Cells[lastRow, lastCol].From == null) break; int row = lastRow; int col = lastCol; lastRow = Cells[row, col].From.Row; lastCol = Cells[row, col].From.Col; CellsControl2.SetColor(lastRow, lastCol, Color.Red); } } } |
2回目以降のテストができるようにします。Shuffleボタンをクリックしたら乱数（0～9までの整数）が生成されCellにセットされます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public partial class Form1 : Form { private void button2_Click(object sender, EventArgs e) { CellsControl2.ClearValues(); Cells = new Cell[MaxRow, MaxCol]; Random random = new Random(); for (int row = 0; row < MaxRow; row++) { for (int col = 0; col < MaxCol; col++) { int r = random.Next(10); Cells[row, col] = new Cell(row, col, r); CellsControl1.SetValue(row, col, r); } } } } |
