ダイクストラ法 (や A*) は、隣接するノード間の距離が一定でない場合を扱えるので、あるノードに到達するパスで、先に見つかったパスよりも短いパスが後から見つかることがある。
たとえば、
graph.asy:
size(100mm,100mm);
void node(pair p, string s) {
filldraw(shift(p)*scale(0.2)*unitcircle, white);
label(s, p);
}
void line(pair p, pair q, string s) {
draw(p--q);
label(s, (p+q)/2+(0.1,0.05));
}
pair s = (0,10);
pair a = s + 1*dir((-1,0));
pair b = s + 2*dir((2,-1));
pair c1 = a + 3*dir((2.6,-2));
pair c2 = b + 1*dir((-0.9,-2));
pair c = (c1+c2)/2;
pair g = c + 1*dir((0,-1));
line(s, a, "1");
line(s, b, "2");
line(a, c, "3");
line(b, c, "1");
line(c, g, "1");
node(g, "G");
node(c, "C");
node(a, "A");
node(b, "B");
node(s, "S");
というグラフで、優先順位付きキューに S だけが入っている状態から探索をはじめる。S の優先順位は 0 である。(優先順位は小さいほど優先されるとする)
この時点でキューに入っている S の中では S が最優先なので、S を取り除き、S から隣接するノードを調べると、A, B が見つかる。A を優先順位 1 でキューに入れ、B を優先順位 2 でキューに入れる。
この時点でキューに入っている A, B の中では A が最優先なので、A を取り除き、A から隣接するノードを調べ、C が見つかるが、ここで見つかった、S から A を経由して C に到達する距離は 1 + 3 = 4 である。C を優先順位 4 でキューに入れる。
この時点でキューに入っている B, C の中では B が最優先なので、B を取り除き、B から隣接するノードを調べ、C がまた見つかる。ここで見つかった、S から B を経由して C に到達する距離は 2 + 1 = 3 である。
ここで、単純に C を優先順位 3 でキューに入れる、と、キューの中で C がふたつになってしまう。さりとて、S-A-C よりも S-B-C のほうが短いので、後から見つかった S-B-C を捨てるわけにもいかない。というわけで、すでにキューに入っている要素の優先順位を書き換える必要が出てくる。
さて、しかし、この迷路の話では斜めには動けないので、隣接するノード間の距離は一定である。
ノード間の距離が一定の場合、後から短いパスが見つかるということはない。そうすると、ダイクストラ法は幅優先探索に等しくなる。
というわけで、この問題にダイクストラ法を適用すると幅優先探索になってしまうので、ダイクストラ法という選択に意味があるだろうか。
なお、A* はヒューリスティック関数によりダイクストラ法よりもマシな探索をするので、その選択には意味がある。
ダイクストラ法に意味があるとしたら、将来への布石だろうか。斜め移動 (距離は sqrt(2)) のサポートが予期されているとか。
既出だったか。