【アルゴリズム】ダイクストラ法で迷路を解きたい

Question

質問概要

ダイクストラ法で迷路を解く際、迷路の隣接行列はどうすればいい？

質問

ダイクストラ法で迷路を最短距離で求める場合なのですが、
色々資料を見て回ったところ、隣接行列を使ってコストを定義するというところにたどり着きました。

しかし、その迷路のコストを定義する隣接行列はどのように生成するのでしょうか？

例えば、6*6の迷路があった場合、隣接行列は6行*6列=36行列となってしまいます。（あってますか？）
そして、隣接しているマス目のコスト（例えば1）を入れると、
1行目は
0 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0
のようになります。

こういった考え方であっているのでしょうか？
もっとスマートなやり方が有る気がします。

そのあたりのお知恵を貸していただけないでしょうか？
よろしくお願いいたします。

Answer 1

例えば、66の迷路があった場合、隣接行列は6行6列=36行列となってしまいます。（あってますか？）

いえ、マス目とマス目を移動するコストを入れますので、36*36の行列になります。

隣接しているマス目のコスト（例えば1）を入れると、

隣接していないところが0の場合、そっちのほうが低コストになってしまいます。巨大な値（全マス目の数より大きな値や無限大）を入れておく必要があります。

Comments

[nnahito]

ご回答ありがとうございます。

> いえ、マス目とマス目を移動するコストを入れますので、36*36の行列になります。
お恥ずかしい……
たしかにそうですねw

> 隣接していないところが0の場合、そっちのほうが低コストになってしまいます。巨大な値（全マス目の数より大きな値や無限大）を入れておく必要があります。
こちら、参考にしていたサイトさんだと、動けるのは1以上の数値のマス目でやっていたので、
そのまま書いておりました。

結局のところ、このやり方が最適というお話でよろしいでしょうか？