最短経路を探すという場合、いくつか方法が考えられます。 もし、スタートからゴールに至るすべての経路がリストアップできるなら、 それぞれで経路長を算出し、最小値をとる経路を選べば良いわけです。 しかし、この方法では、すべての経路をリストアップする、という 過程が非常に面倒なものとなります（京都市のような町なら...）。 そこで、ダイクストラ法と呼ばれる方法を使うことにします。
最短経路を求めるために、まず、各交差点からゴールまでの 最短距離を求めます。その次にそれをもとに最短経路を求めます。
最短経路を求める前に、ゴールまでの最短距離がわかると、なぜ 最短経路が求まるかを説明しておきましょう。
ある交差点[A]から、ゴール[G]までの最短経路を求めたいとします。 交差点[A]から道路がつながっている交差点として [B] [C] [D]が あり、
|
このように各交差点のゴールまでの最短経路を求めることができると、 最短経路の探索ができます。そこで、次に、各交差点からゴールまでの 最短経路を求める方法を考えることにします。
※ 一見すると「隣接する交差点からゴールまでの最短経路と、その交差点までの 距離の和が、『今いる交差点のゴールまでの最短経路』と等しい」としても いいように思えます。しかし、コンピュータで小数変数を使う場合に、 ごく微少な誤差のために、直接代入した場合を除き『等しい』は成立しない 可能性が生じます。特に演算結果を比較する場合などは要注意です。 そのため『最小』という表現、プログラムにしたほうが安全です。 どうしても、『等しい』ことを 判定したい場合の手段としては、差の絶対値が十分小さい、などの評価を プログラムで行うことになります。
まず、第一段階として、各交差点からのゴールまでの最短距離を求めましょう。 そのために、本演習で推している方法は、このような場合に一般的に 用いられる Dijkstra(ダイクストラ)法です。
ダイクストラ法では、交差点を２つのグループに分けます。一つは 基準交差点（ここではゴール）までの最短距離が確定している交差点群、 もう一つは未確定の ものです。最初はすべての交差点が未確定ですが、１つずつ確定していき、 最後にすべての交差点を確定します。確定した交差点集合をＶ、未確定の 交差点集合をＵをします。
それぞれの交差点には、基準交差点までの、現在のところわかっている 最短経路の距離を表す変数 distance を持たせます。この distanceは Ｖに含まれる 交差点では真の最短距離になりますが（つまり、全部Ｖに入った段階で 全部真の最短距離）、Ｕに含まれる交差点ではそうとは限りません。
さて、ある時点でこのように交差点がＵ・Ｖに分かれているときに、
Ｕから交差点をＶに移していきます（Ｖは確定しているので、
もうなにもしない）。まず、Ｕに含まれるそれぞれの交差点の distance を
計算します。distance は
途中でＶに属する、最短距離確定済の交差点のみを通る最短経路での
距離とします。このことは、Ｖに隣接する交差点のみが distance を
計算できる、ということです。またＶ内の交差点の複数とつながって
いる場合は、当然最も経路が短くなる交差点経由で計算します。
Ｖに隣接していない交差点は対象外とします。
この distance の定まった交差点の中から、distance が最小である
交差点を選びます（等しいのが二つ以上ある場合は適当にどれかひとつ）。
この交差点は以下に述べる理由で、Ｖに移してしまって構いません。
この手順を繰り返すことで、一つずつ交差点をＵからＶに移していくと、
最後にすべての交差点で最短距離が確定します。
また、適当に選んだ交差点の distance が最短ではない可能性の 有無ですが、これは有り得ます。ある交差点の、 Ｖにつながる道路が実はぐにゃぐにゃの山道、 ところがすぐとなりの交差点からＶにつながる道路はトンネルで一直線、 だったら迷わずトンネルを通りますよね（紅葉を見たい、とかでなければ）。 このように、Ｖに隣接していても、別の交差点を経由したほうが近い、 という場合は有り得ます。
Ｕ／Ｖを区別するには、俗に「フラグ」と呼ばれる変数を用意します。 フラグというのは、ある状態が満たされたかどうかを記憶する ための変数を指す言葉で、大抵は０と０以外（１など）が代入されます。 ゲームなどでも「フラグを立てる」などといいますが、ゲームのプログラムを つくる側の用語がそのまま使われているものと言えます。 つまり、最初は各交差点のフラグをクリアしておき（Ｕを意味する）、 確定するときにフラグをセットする（Ｖを意味する）ことで区別する わけです。これは if 文で簡単にわかります。
つぎに distance が定まらない交差点の扱いです。これもフラグを別に
作っても良いのですが、今回は
distance に有り得ないような大きな値を代入することにします。
というのも、distance を決定した後で「distanceが最小のものを選ぶ」
ため、distanceを大きな値にしておけば選ばれる心配がない＝除外したのと
等価になります。
しかも、このdistanceは
この案をもとにより詳細にプログラムを考えていくと、
さて、実際にプログラムはどう進むかというと、１週目は当然、 唯一０を設定したゴールの交差点が確定し、それに隣接する交差点の distance が（大きな数から最短距離に）更新されます。そのなかで、最も 数値の小さいものは、上の理論によって２週目に確定します。 以下、その操作が続きます。
以上がダイクストラ法なのですが、｛はっきり｜なんとなく｝わかりますか?
より直感的なのですが、時間のかかる方法もお話ししておきましょう。 その方法は、用意する変数はdistanceにあたる数値を格納しておくためだけの ものです。フラグは終了を判定するためだけに、用意します。
前回の最後にやり残した方法です。いっそのこと、各交差点の ゴールまでの最短距離を途中の経路を無視して、直線距離で結ぶと どうなるでしょう。プログラムは非常に簡単になりますが、 京都のような碁盤の目の町ならともかく、複雑な地図上では、 はまってしまいます。人間なら、もと来た道をもどったりは しないのですが、単に距離だけをみて動くようなプログラムをつくると、 行ったり来たりすることになります。
さて、以上のように、各交差点からゴールまでの最短経路を通ったときの 距離は求まりました。一番最初に説明した方法を用いることで、 最短経路は求まることでしょう。
ただ、気づいた人も多いと思うのですが、最短経路を出すには、 もう少しスマートかもしれない方法があります。最短距離を求める 段階で、「どの交差点に向かえば最短経路か」はわかっています （最短距離の更新をする段階で）。変数を１種類増やして、 どの交差点にいけばいいかを残しておけば、距離をいじる必要も なくなります。変数を一つ増やすか、すこし複雑な方法にするか、 それはプログラマの考え方とも言えます。