Gerd AltmannによるPixabayからの画像
青木です。paizaラーニング担当のエンジニアです。
皆さん、「ダイクストラ法」というアルゴリズムは知っていますか？
ダイクストラ法とは、グラフ上にある2点間の最短経路を求めるアルゴリズムで、考えられる全経路を挙げていくよりも効率的に求めることができます。
このアルゴリズムはさまざまな分野で応用されており、私たちの身近なところでいうとカーナビの経路探索や鉄道の経路案内にも用いられています。
今回は原理ではなく、問題に対する実装を通してプログラムを組む方法を具体的なJavaのコードで示しながら解説していきます。（アルゴリズム自体について詳しく知りたい方はWikipediaを参照してみてください）
なお、本記事で扱う問題は「レベルアップ問題集」で取り組めるようになっていますので、実際にコードを書きながら進めてみてください。
またダイクストラ法は、paizaスキルチェックの高難度の問題の解法として使われることがあります。ぜひマスターしてSランクに挑戦してみましょう！
（前置き）グリッドグラフとは
グラフとは以下の図のようなノードとエッジの集まりのことです。
ただ、プログラム上でこのようなグラフを扱おうとすると、データ構造が少し煩雑でイメージしにくいので、今回はイメージしやすいグリッド（格子）を対象にした問題だけを扱います。
グリッドグラフとは、グリッドに対応させたグラフのことです。
グリッドはプログラミング問題でもよく出題され、二次元配列で扱うことができます。では、さっそく問題を解いていきましょう！
ダイクストラ法を使って解く問題
以降、Javaで解説している関係上、問題ページへのURLはJavaになっていますが、Python、PHP、Ruby、C#など他の言語でも解答できます。「グリッド版ダイクストラ問題セット」から選択してください。
現在問題集からはJavaのみ提出後ページから解答例となるコードを参照可能です。また、本記事の各問題解説の最後にも載せていますので参考にしてみてください。
他のプログラミング言語の経験はあるけど、Javaは初めてという方は、paizaラーニングの「Java入門編」を受講すると理解が深まると思います。
問題0: グリッド上の移動
まずはウォーミングアップ。グリッドを扱うことに慣れるための問題です。
問題ページはこちら
問題概要：
グリッド状の盤面の左上からスタートして、「右、下、右、上、左」と順に移動したときの経路上のマスのコストの合計を求めてください。
経路上のマスには、スタートとゴールのマスも含むものとします。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
コストの合計を 1 行で出力してください。
考え方：
たとえば、入力が以下のようなときは、縦幅2、横幅5の図のようなグリッドを表しています。
2 5 0 1 2 3 4 5 6 7 8 9
今回は「右、下、右、上、左と順に移動する」というルールがあるため、下図のような経路をたどることになります。
ですので、
0 + 1 + 6 + 7 + 2 + 1 = 17
を求めることができれば正解です。 同じマスを2回通った場合は、コストを2回足します。
解答例（解き方のコツ）：
左右の位置をx座標、上下の位置をy座標で考えてみましょう。以下のとおり、配列のdxとdyを作ってみます。
final static int[] dx = {1, 0, -1, 0}; final static int[] dy = {0, -1, 0, 1}; final static int R = 0, U = 1, L = 2, D = 3;
RはRight、UはUp、LはLeft、DはDownを表しています。動きがRのときは、横の動きがdx[R] = dx[0] = 1。縦の動きがdy[R] = dy[0] = 0。これでxy座標上でx方向へ1つ座標が動くことを表しています。同様に他のdx[U]なども座標の動きを表しています。
以下のようなコードを実行すると、x, yを右に移動できます。例えば、(x, y) = (0, 0)のときに、以下のコードを実行すると、(1, 0)に更新されて右に移動できます。
x += dx[R]; y += dy[R]; // 右へ移動
同様に、上、左、下へは次のようにすれば移動できます。
x += dx[U]; y += dy[U]; // 上へ移動 x += dx[L]; y += dy[L]; // 左へ移動 x += dx[D]; y += dy[D]; // 下へ移動
これらの機能を使って、今回は右、下、右、上、左と移動すればOKです。移動途中にコストも足し合わせるようにすれば解くことができます。
問題0の解答例コードはこちら
問題1: 幅優先探索 - 迷路
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、左上のスタートから右下のゴールまで移動するときに通るマスの最小の個数を求めてください。ただし、0のマスは通れて、1のマスは通れません。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目の値です。
期待する出力：
ゴールまで移動するときに通るマスの最小の個数を 1 行で出力してください。
考え方：
たとえば、以下のような入力が与えられた場合について考えてみます。
3 6 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0
図のような経路をたどれば、最小ステップでゴールまで移動できます。
解答例（解き方のコツ）：
マスの位置の状態は、以下のようにx（横方向）, y（縦方向）の2つのデータをまとめて扱う必要があります。 言語に合わせて、タプル、構造体、クラスなどを使ってください。
static class State { int x, y; ... }
解答例では、幅優先探索（Breadth First Search）のメソッドをbfsとして切り出しています。 sxとsyはスタートの位置、gxとgyはゴールの位置を表します。
static int bfs(int h, int w, int[][] t, int sx, int sy, int gx, int gy) { ... }
bfsでは、未チェックの移動候補の状態を扱うopenリストと チェック済みの状態を扱うclosedリストを用意しています。
LinkedList<State> open = new LinkedList<>(); Set<State> closed = new HashSet<>();
openリストには、初期状態としてスタートの位置(0, 0)を入れておきます。
State initialState = new State(sx, sy);
open.add(initialState);
幅優先探索のコードから、余計なものを除くと以下のようになります。
int cost = 1; while (true) { LinkedList<State> tmpQ = new LinkedList<>(); while (!open.isEmpty()) { State st = open.poll(); for (int i=0; i<4; i++) { int nx = st.x + dx[i]; int ny = st.y + dy[i]; tmpQ.add(new State(nx, ny)); } } open = tmpQ; cost ++; }
内側のfor文ではopenリストから1つずつ状態を取り出し、その状態がゴールにたどり着いていないなら、4方向それぞれに移動した状態を新規に作ってやり、次のステップで使うopenリスト(tmpQ)に追加しています。
例えば、(x, y) = (2, 3)という状態からは、右へ移動した(3, 3)と、上へ移動した(2, 2)、左へ移動した(1, 3)、下へ移動した(2, 4)という4つの状態を作ることができますよね。
あるステップの候補の状態をすべてチェックしたら、openリストをそのステップで作成したtmpQで置き換え、変数のcostを1増やしてやり、次のステップへ移っていきます。
open = tmpQ;
cost ++;
上のコードだけではプログラムが終了しないので、答えを見つけたら終了するように条件を追加します。 ゴールにたどりついたときのcostが求めたい移動したマスの数になっているので、それを返せばOKです。
if (st.x == gx && st.y == gy) return cost;
他の例外も条件分岐で処理します。
以下のコードで、状態の候補が範囲外ならばチェックしないようにします。
if (!(0 <= nx && nx < w && 0 <= ny && ny < h)) continue;
同様に以下では、1のマスは通れないので無視するようにしました。
if (t[st.y][st.x] == 1) continue;
もしチェックしようとしている状態がclosedリストに含まれているなら再チェックしないようにし、未チェックの状態はclosedリストに新しく追加しておきます。
closedリストの処理がなくてもプログラムは動作しますが速度が非常に遅くなります。ここが高速化のポイントです。
if (closed.contains(st)) continue; closed.add(st);
幅優先探索の実装はやや複雑ですが、これができればダイクストラ法の骨格はほぼでき上がりです。 ダイクストラ法を理解するための要にもなるので、時間をかけてでも内容をしっかりつかんでおいてください。
問題1の解答例コードはこちら
問題2: ダイクストラ法 - 最短経路のコスト
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、左上のスタートから右下のゴールまで移動するときに通るマスのコストの合計の最小値を求めてください。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
コストの合計の最小値を 1 行で出力してください。
考え方：
たとえば、以下のような入力が与えられた場合について考えてみます。
3 6 0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2
図のような経路をたどれば、最小のコストでゴールまで移動できます。
解答例（解き方のコツ）：
さきほど解いた問題1のコードを修正し、ダイクストラ法に対応させていきます。
問題1の幅優先探索では、状態としてxとyだけを使っていましたが、ダイクストラ法を使う際は、状態にひもづくcostを追加しています。
static class State implements Comparable<State> { int x, y; int cost; ... }
今回はcostの大小でオブジェクトを比較したいので、Javaの場合はcompareToメソッドを記述しておきます。
@Override public int compareTo(State that) { return this.cost - that.cost; }
さきほど書いたbfsメソッドの名前をdijkstraに変更します。
static int dijkstra(int h, int w, int[][] t, int sx, int sy, int gx, int gy) { ... }
幅優先探索のときは、コストが1ずつ増えるだけだったので、以下のように状態にひもづくコストを管理する変数を1つだけ用意して全体で共通のものとして使っていました。
int cost = 1; while (true) { LinkedList<State> tmpQ = new LinkedList<>(); while (!open.isEmpty()) { ... } open = tmpQ; cost ++; }
今回はコストを状態ごとに個別に紐付けられるようにしたので、上の無限ループを削除し、状態に個別にひもづいたコストを更新するコードに整えます。 すると、ループのネストが一段減ってコードが以下のようにすっきりします。
static int dijkstra(int h, int w, int[][] t, int sx, int sy, int gx, int gy) { LinkedList<State> open = new LinkeList<>(); Set<State> closed = new HashSet<>(); State initialState = new State(sx, sy, t[sy][sx]); open.add(initialState); while (!open.isEmpty()) { State st = open.poll(); if (st.x == gx && st.y == gy) return st.cost; if (closed.contains(st)) continue; closed.add(st); for (int i=0; i<4; i++) { int nx = st.x + dx[i]; int ny = st.y + dy[i]; if (!(0 <= nx && nx < w && 0 <= ny && ny < h)) continue; int ncost = st.cost + t[ny][nx]; open.add(new State(nx, ny, ncost)); } } return -1; }
あとは、openリストを優先度付きキュー（いわゆるヒープ）に変更します。Javaの場合はPriorityQueueクラスが使えます。
PriorityQueue<State> open = new PriorityQueue<>();
以上でダイクストラ法で問題2を解くコードの完成です。
今回知りたいのはゴールまでの最小のコストでした。 openリストが優先度付きキューで作られているおかげで、必ずコストが小さい状態から順に処理されます。 このため、ゴールへの経路は複数通りありますが、最初に見つかったゴールの状態のコストが知りたい最小のコストになります。
ちなみに優先度付きキューとは…
- キューに対して要素を優先度付きで追加する。
- 最も高い優先度を持つ要素をキューから取り除き、それを返す。
- (オプション) 最も高い優先度を持つ要素を取り除くことなく参照する。
- (オプション) 指定した要素を取り除くことなく優先度を変更する。
出典：Wikipedia
（参考）実際のデータを当てはめて理解を深める
ここで、アルゴリズムの理解を深めるために、実際のデータを当てはめてアルゴリズムの動作を詳細に確認してみましょう。単調な操作の繰り返しにはなるので、すでに理解が十分であれば適宜読み飛ばしてください。
ここまでしっかり確認できれば、ダイクストラの流れが身に染み込んだと思います。
ただ、「こんなに大変なダイクストラ法、本当に効率がいいの…？」と思った方もいらっしゃるかもしれませんね。
プログラムを実行すると、closedリストによる重複状態の排除のおかげで、状態をチェックして新しく生成する操作が「マスの総数 × 4回以下」になり、計算時間を見積もることができ、しかも高速です。
スキルチェックで1000 × 1000のグリッドを扱う問題でも制限時間内に実行できるかと思います。
問題2の解答例コードはこちら
問題3: ダイクストラ法 - 経路復元
ダイクストラ法は、一般的には最短経路を求めるアルゴリズムとして知られています。さきほどの問題では、ゴールまでの「最小コスト」を計算しただけだったので、今度は「最小コストとなる経路」も求めます。
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまで移動するときに通るマスのコストの合計の最小値を求めてください。
さらに対応する経路をゴールからスタートまでの順序で出力してください。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
コストの合計の最小値を1行目に出力してください。
続けて、ゴールからスタートまでの経路を以下のように盤面の並びとして出力してください。
--
盤面_1
--
盤面_2
...
--
盤面_n・nは最短経路上のマスの数です。
・盤面_k (1 ≦ k ≦ n) はゴールからいくつ前のマスにプレイヤーがいるかを表しています。
・盤面_1はゴールのマスにプレイヤーがいることを表す盤面です。盤面_k (1 ≦ k ≦ n) は次の形式で出力してください。
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・t_{i,j}の左には半角スペースを出力してください。
・ただし、通るマスにプレイヤーがいるマスの左には、半角スペースの代わりに*を出力してください。
考え方：
たとえば、以下のような入力が与えられた場合について考えてみます。
3 6 0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2
マスの左側に*をつけて以下のような形式で最短コストとなる経路を出力します。 逆順にたどるようになっているのは、実装を容易にするためです。
17 -- 0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3*2 -- 0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9*3 2 -- 0 3 1 4 1 5 9 2 6 5*3 5 3 9 7 9 3 2 -- 0 3 1 4*1 5 9 2 6 5 3 5 3 9 7 9 3 2 -- 0 3 1*4 1 5 9 2 6 5 3 5 3 9 7 9 3 2 -- 0 3*1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2 -- 0*3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2 -- *0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2
解答例（解き方のコツ）：
現在の状態の1つ前の状態を覚えておくためStateにrefを追加します。
static class State implements Comparable<State> { int x, y; int cost; State ref; ... }
初期状態のrefはnullにして
State initialState = new State(sx, sy, t[sy][sx], null);
新しい状態を作るときには、今の状態を記憶させるようにします。
open.add(new State(nx, ny, ncost, st));
dijkstraメソッドは最短コストではなくて、終了状態を返すように修正しておきます。
if (st.x == gx && st.y == gy) return st;
返ってきた終了状態から順に、refを使って経路を逆順に辿りつつdispメソッドで出力します。 初期状態のrefはnullなので、nullになったら終了します。
State st = dijkstra(h, w, t, 0, 0, w-1, h-1); System.out.println(st.cost); while (st != null) { disp(h, w, t, st.x, st.y); st = st.ref; }
あとは、個別の状態に対応する位置を出力するdispメソッドを実装すれば完成です。
static void disp(int h, int w, int[][] t, int x, int y) { System.out.println("--"); for (int i=0; i<h; i++) { for (int j=0; j<w; j++) { System.out.print(j == x && i == y ? "*" : " "); System.out.print(t[i][j]); } System.out.println(); } }
問題3の解答例コードはこちら
問題4: 拡張ダイクストラ - コストを0にできるチケット
問題ページはこちら
続いて「コストを0にできるチケットが付与される」という条件を増やし、グラフを拡張してダイクストラ法で解く方法を考えます。
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまで移動するときに通るマスのコストの合計の最小値を求めてください。
ただし、1つのマスのコストを0にできるチケットをn枚使えます。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}
n・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
・最後の行ではチケットの枚数 n が与えられます。
期待する出力：
コストの合計の最小値を 1 行目に出力してください。
考え方：
たとえば、以下のような入力が与えられた場合について考えてみます。
5 12 0 1 1 1 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 1 9 9 1 1 1 1 9 9 9 9 9 1 9 9 1 9 2 9 9 1 1 1 1 1 9 9 1 1 1 1 2 1 9 9 9 9 9 9 1 1
もしチケットが0枚であれば、問題2と同じように最小コストの経路を求めればよいため、以下のような経路になります。
この場合、コストは25です。
*0*1 1 1 9 9 9 9*1*1*1*1 1*1 1 1 1 9 9 9*1 9 9*1 1*1 1 9 9 9 9 9*1 9 9*1 9*2 9 9*1*1*1*1*1 9 9*1 1*1*1*2*1 9 9 9 9 9 9*1
チケットが1枚なら、図の位置の9のコストを0にするのが最小コストとなり、このときのコストは20です。
*0*1 1 1 9 9 9 9*1*1*1*1 1*1*1*1*1 9 9 9*1 9 9*1 1 1 1 9*9 9 9 9*1 9 9*1 9 2 9 9*1*1*1*1*1 9 9*1 1 1 1 2 1 9 9 9 9 9 9*1
チケットが2枚なら、ゴール付近の2つの9のコストを0にするのが最小コストとなり、このときのコストは17です。
*0*1 1 1 9 9 9 9 1 1 1 1 1*1 1 1 1 9 9 9 1 9 9 1 1*1 1 9 9 9 9 9 1 9 9 1 9*2 9 9*1*1*1*1*1*9*9*1 1*1*1*2*1 9 9 9 9 9 9*1
解答例（解き方のコツ）：
コストを求めればいいので、問題2のコードを少し修正するだけで解くことができます。
具体的には、位置(x, y)に加えて、利用可能な残りのチケット枚数ticketを追加してやります。
static class State implements Comparable<State> { int x, y; int ticket; int cost; ... }
新しい状態を作成する際に、チケットを利用する場合と利用しない場合の2つの状態を作るようにします。
int ncost1 = st.cost + t[ny][nx]; open.add(new State(nx, ny, st.ticket, ncost1)); if (st.ticket > 0) { int ncost2 = st.cost; open.add(new State(nx, ny, st.ticket - 1, ncost2)); }
これで、ticketも考慮できるようになりました。
状態と状態を結んでできる「グラフ」をチケットの分だけ拡張しているので、このようなアルゴリズムを拡張ダイクストラ法と呼んだりします。
問題4の解答例コードはこちら
問題5: ゴールのマスが複数
次に、ゴールのマスが複数ある場合のダイクストラ法の適用方法を確認します。
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから最下段のゴールへ移動するときのコストの合計の最小値を求めてください。
ゴールはw個あるので、それぞれのゴールにへ移動する最小コストを求めてください。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
次の形式で最下段のw個の各ゴールへの最小値を改行区切りで出力してください。
t_{h-1,0}へ移動するコストの最小値
t_{h-1,1}へ移動するコストの最小値
...
t_{h-1,w}へ移動するコストの最小値
考え方：
以下のようなグリッドが対象ならば、
0 3 1 4 1 5 9 2 6 5 3 5 3 9 7 9 3 2
最下段の6点それぞれへの移動コストの最小値は次のようになります。
12 // 0 -> 9 -> 3と移動 14 // 0 -> 3 -> 2 -> 9と移動 17 // 0 -> 3 -> 1 -> 6 -> 7と移動 22 // 3 -> 1 -> 4 -> 5 -> 9と移動 15 // 0 -> 3 -> 1 -> 4 -> 1 -> 3 -> 3と移動 17 // 0 -> 3 -> 1 -> 4 -> 1 -> 3 -> 3 -> 2と移動
解答例（解き方のコツ）：
ゴールのマスの数だけダイクストラ法を適用してもよいですが、実は1回のダイクストラ法で効率よく解くことができます。
dijkstraメソッドを打ち切るreturnを削除して、代わりに最下段のマスの状態についての最小コストを保存するようにします。
if (st.y == gy)
costs[st.x] = st.cost;
このようにすることで、ある1つのスタートのマスから、他のすべてのマスへの最小の移動コストを一度に求めることができます。便利なテクニックですのでぜひ覚えておいてください！
問題5の解答例コードはこちら
問題6: 1つの中継点
さらにダイクストラ法の類題を確認していきます。問題6は途中で通る中継点を決めたときの最短経路を求める問題です。
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右上のマスを経由して右下のゴールまで移動するときに通る各マスのコストの合計の最小値を求めてください。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
コストの合計の最小値を 1 行で出力してください。
考え方：
以下のようなグリッドの場合、どのような経路を通らなければならないか確認します。
1 5 9 5 1 2 9 1 2 2 1 9 2 9 9 2 2 1 1 1
左上から右上への移動が最小コストとなる経路は以下の通りです。コストは、1+2+1+2+2+1+2+1+2+2+1=17となります。
*1 5 9 5*1 *2 9*1*2*2 *1 9*2 9 9 *2*2*1 1 1
続けて右上から右下への移動が最小コストとなる経路は下の通りで、1+2+2+1+2+1+1+1=11となります。
1 5 9 5*1 2 9*1*2*2 1 9*2 9 9 2 2*1*1*1
よって合計の最小コストは、17+11-1=27となります。1を引いているのは、右上のマスを2回数えているためです。
解答例（解き方のコツ）：
最小コストとなる経路を2つ求める方法で解くことができます。
ですので、以下のように2回ダイクストラ法を呼び出してあげれば答えが求まります。
int cost1 = dijkstra(h, w, t, 0, 0, w-1, 0); int cost2 = dijkstra(h, w, t, w-1, h-1, w-1, 0); System.out.println(cost1 + cost2 - t[0][w-1]);
ダイクストラ法が書ければ、余裕ですね。 もちろん経由する点の数が増えても同様に解くことができます。
ただし、全てのマスの組の最小コストが必要な場合は、「ワーシャルフロイド法」というもののほうが効率がよくなりますし、複数の点を経由する順序も考慮が必要な場合には「巡回セールスマン問題」と呼ばれる問題になるため、別のアプローチが必要になります。
ちなみに「巡回セールスマン問題」については、paizaラーニングの動画講座「アルゴリズム入門編」の中で解説していますので興味がある方はぜひごらんください。
問題6の解答例コードはこちら
問題7: コストを変更 - 経由地の最大コストの最小値
さらに類題を解きます。ここまでは経路上の数値の合計をコストとしていましたが、そうではない場合について考えてみましょう。
問題ページはこちら
問題概要：
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまでなるべくコストが小さなマスを通って、ゴールまで移動してください。
ゴールするまでに通るマスのコストの最大値が最小になるような経路で移動し、そのコストの最大値を出力してください。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
コストの最大値を 1 行で出力してください。
考え方：
問題に「最大値の最小」という言葉が出てきて紛らわしいので、今回も入力例を確認して問題を理解します。
以下のようなグリッドを考えます。
0 1 1 4 1 5 9 2 5 3 1 5 3 3 3 3 1 2
経路上のマスの合計値は以下の経路を通ると最小となりますが、経路上のマスの最大の数値は4となります。
*0*1*1*4*1 5 9 2 5 3*1 5 3 3 3 3*1*2
一方で、以下のような経路を通ると、経路上のマスの最大の数値は3となり、この値が先ほどの経路よりも小さくなりました。
今回は経路上のマスの最大の数値を最小にしたいので、これが最小の3となるこの経路を求める必要があります。
*0*1 1 4 1 5 9*2 5 3 1 5 3*3*3*3*1*2
解答例（解き方のコツ）：
以下のようにコストの更新方法を変えると解けます。以前までは経路上のすべてのマスのコストを足し合わせてましたが、今回は最大値を更新していくようにしています。
int ncost = Math.max(st.cost, t[ny][nx]);
ダイクストラ法は、次の状態のコストが前の状態のコストから減少することがない場合に適用することができます。すなわち、単調増加する場合にのみ適用できます。
今回はコストを途中で通ったマスの最大値で更新しているため、コストがそのままか大きくなることしかないので、ダイクストラ法が適用可能です。
ちなみに、経路上に負のコストが出てくる最短経路問題では、コスト更新の単調増加の前提がくずれてしまいダイクストラ法は使えなくなりますので、注意してください。
そのような場合の最短経路問題では「ベルマンフォード法」と呼ばれるアルゴリズムが使われます。
問題7の解答例コードはこちら
問題8: 全てのマスを連結するときの最小コスト
最後の問題までたどり着きました。張り切っていきましょう！
問題ページはこちら
グリッド状の盤面が与えられます。盤面上で2つのマスを連結するコストは2つのマスの数値の積です。上下左右にマスを連結して、すべてのマスがマスを介して連結するための最小のコストを求めてください。
初期の盤面では各マスはいずれのマスとも連結していないものとします。
入力される値：
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}・1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・続く h 行の各行では i 行目 (0 ≦ i < h) には、盤面が与えられます。
・t_{i,j} は i 行目の j 列目のコストです。
期待する出力：
最小のコストを 1 行で出力してください。
考え方：
今回は経路を求めるのではなく、マス同士を連結する方法を求めす。
以下のようなグリッドを例に考えます。
3 1 4 1 5 9 2 6 5
このグリッド上で2と6のマスを連結するコストは、2つのマスを掛け合わせた値である2 x 6 = 12となります。
3 1 4 1 5 9 2-6 5
すべてのマスを縦横につないで、連結された状態にする必要があります。たとえば、以下のような場合の合計のコストは、3x1+1x2+5x6+5x1+1x4+4x9+9x5=125となります。
3 1-4 | | | 1-5 9 | | | 2 6 5
この合計のコストを最小にするのが今回の問題です。 最小となる接続方法は次のようになり、このときのコストは3x1+1x4+4x9+3x1+1x5+1x2+2x6+6x5=95となります。
3-1-4 | | | 1-5 9 | 2-6-5
解答例（解き方のコツ）：
いずれか1つの点から開始する、ほぼダイクストラ法に近いやり方を適用することで解けます。
closedリストへマスを追加する処理をマスを連結する操作と対応させることができます。 そのためclosedリストに追加したマスに対応するコストを全体のコストに足し合わせてやります。
closed.add(st);
cost += st.cost;
closedリストにすべてのマスが追加されたときの合計コストが答えとなります。
if (closed.size() == w * h) return cost;
この問題はいわゆるグラフの最小全域木を求める問題です。
最小全域木は、今回のようにダイクストラ法からの若干のコード修正で求めることができます。このようなアルゴリズムは「プリム法」と呼ばれています。
問題8の解答例コードはこちら
まとめ
今回はダイクストラ法をグリッドグラフに適用して最短経路問題を解く方法を解説しました。
問題0、1は幅優先探索の導入、問題2はダイクストラ法の導入、問題3は実際のダイクストラ法で求めた経路の復元、問題4、5、6、7、8は類題になります。
実は問題2まで理解することができれば、残りの問題は微修正で解けるようになっています。
初めのうちは難しく感じるかもしれませんが、すべて自分で実装してみて理解を深め、ダイクストラ力を鍛えてください。この記事がみなさんのpaizaスキルチェックでのSランク取得の参考になればと思います。
もし「こういったところがもう少し説明がほしい」というのがあれば、ご意見を送っていただけると助かります。
paizaの公式Twitterアカウントはこちら、paizaラーニングの公式Twitterアカウントはこちらです。
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
