最短距離を求める問題（ダイクストラ法）の原理

質問

グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。
このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。
また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。

”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。”

ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。

他に何かイメージがつかみやすい説明があるでしょうか。
また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。

サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。

よろしくお願いします。

回答No.4

Tacosan

ちなみにダイクストラ法そのものは「ちょう基本」です.

というか, これが分からないようだと他のグラフ理論的なアルゴリズムはきついんじゃないかな.

お礼

回答ありがとうございます。
例えば、2次方程式の解の公式（中高数学）を用いて解を示すという問題がプログラムの第一歩だと思います（ハローワールドの次ぐらい）。アルゴリズム的には例外処理ぐらいのものですね。決定論的プログラムとも言えると思います。（プログラミングですらないとも言えそうです。）ダイクストラ法は基本的と言ってもさすがにそこまではいかないと思いますが。

ダイクストラ法は動的プログラミングに含まれるのでしょうか。名前入りアルゴリズムだったり適用が限定されていたりするから即刻理解できるようなものではないのではないかと思うのですが。

今一度じっくり見てみます。

回答No.3

maru_yoshi_

なんか屁理屈で議論をしたいだけなのかなぁ？
> 板と重力の向きに対する説明が文章中にないのでイメージができないのです。
惑星（地球）上では重力は下向きです。常識でしょう。
板の上に載っているとしているのだから、きっと水平でしょう。
ただし水平かどうかは余り関係なくて、板の上に載っているのだからそれぞれのビー玉の間の紐が直線になっていなくてたるんでいるということが重要。

> ビー玉は真ん中が繰り抜かれて紐（経路の相当）が通っているという感じでしょうか。
ビー玉と紐のつなぎかたなど本質とは全く関係ない（だから、「グラフを工作する」としか書いていない）。紐を通そうが、接着剤でつけようがどうでもいい話。
でもそのイメージで考えると数珠みたいなものを考えればいいかもしれない。

> ぶどうの房のような振り子がブラブラ揺れているということでしょうか。
そう考えていいでしょう。ただし、ビー玉の大きさは無視して考えることが重要。
そうしないと途中のビー玉が邪魔になって最短経路が直線にならない、などというよけな心配が出てくる。

スタートからゴールまでの紐が一直線になる経路が最短経路なんだけど、その一直線にするために両端（スタート、ゴール）から引っ張ることをやりたい。
その方法（力のかけ方）に重力を使っているんです。もっと単純に両端から引っ張ると書いてあったほうが分かったのかな？
そう考えれば、板を取り除くかなくても、ビー玉が自由に転がるように傾けるだけでもよい。

単純に考えてみればいいのに。
ABC3点があり、それぞれの間の距離が
A-B:3cm
B-C:5cm
A-C:7cm
であった時、スタートをA、ゴールをBとすると最短経路はA-BでありA-C-Bの経路でないことはすぐにわかる。
これをビー玉と紐の考え方で、AをもってB,Cを落下させるとA-B,A-Cが直線になるがゴールがBなので、最短経路がA-Bの経路になる。

ABCD4点(A-B:3cm, B-C:5cm, C-D:7cm, D-A:2cm),スタート:A、ゴール:C
という条件ならA-B-Cは一直線になるけど、A-D-Cは紐がたるんでいる。
従って、A-B-Cが最短経路になる。
ここで、B-Dが0.5cmでつながっているとすると、A-B間はA-D-Bのほうが短くなりA-Bを直接結ぶ紐はたるんで、最短経路はA-D-B-Cになる。
さら、A-C間が6cmの紐で直接つながっていれば、一直線になるのはA-Cが直接つながっている経路になるので、最短経路はA-Cになる（逆にA-Cが7.5cmより長ければ、A-D-B-C）。

お礼

大変詳細なご説明をありがとうございます。
紐が弛む・弛まないという議論は距離の長短と完全にリンクするので理解できます。アルゴリズム化するには探し方の順序というところがポイントになると思います。
四角形の例で、AC=6を除外してBD=0.5が成立している場合を考えます。
AD(2)+DC(7)=9
AB(3)+BC(5)=8
AD(2)+DB(0.5)+BC(5)=7.5
3番目が最短であることを見破っていくにはどうするのだろうかということですね。

スタートをつまんで重力に従ってぶら下げたらわかるというのが趣旨だと思います。ゴールの玉のぶら下がり具合をみたらわかるということですが、最短コースがわかるからぶら下がり方がわかるという風に思えるわけで、ぶら下がり方から最短コースがわかるというところがどうも理解しにくいのですが。今一度見てみます。

回答No.2

maru_yoshi_

> 板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。
逆に、なぜこのように思うのか理解できません。

「スタートの頂点にあたるビー玉だけをつまむ。」のだからその「スタートの頂点にあたるビー玉」は落下しません。
つまり全部ではないです。
スタートからゴールまでが一直線になれは、その経路以外の紐はどこかでたるんでいるはず。
たるんでいるということは、経路が長くなっているのでそのたるんでいる経路は最短ではない。
ここまでは結構単純だと思うんだけど。

お礼

回答有難うございます。
　先の引用文の中で板とか落下とか書いてあります。落下なので重力の向きが規定されているはずで、とすると板と重力の向きに対する説明が文章中にないのでイメージができないのです。その辺りはどうでしょうか。ビー玉が乗っているというのだから板は水平なのだろうと思いますが。
ビー玉は真ん中が繰り抜かれて紐（経路の相当）が通っているという感じでしょうか。そしてそれがすべらないとか。そのあと落下するからブランコあるいは振り子のようになるということでしょうか。で、スタートだけが落ちないようになっているとしたらぶどうの房のような振り子がブラブラ揺れているということでしょうか。たぶん意図するところがずれていくのではないかと思うのですが。イメージがあっているでしょうか。

回答No.1

f272

Wikiの説明には紐の長さが辺の重みに対応すると言うことがかかれていないように思う。これはあたり前だから省略しているのかな？

> 板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。

全部，落下するけど紐で結ばれているのだから途中で止まるよね。そしてどのビー玉が先に止まるのかは紐の長さに関係していることは明らかだろう。
ここに書かれている説明でアルゴリズムが理解できないのなら，実際のプログラムをステップ実行してループが回るごとに最短経路上の次のノードが決定されていくことを確認してください。

お礼

回答有難うございます。
イメージですが、スタートの点だけが固定されている複雑な数珠のようなものが振り子のように揺れるイメージになります。
どこから先に止まるかというのは単純ではないように思うのですが。全体として剛体のように揺れているから。そういうイメージではないようですね。
　ロッククライミングのハーケンの打ち込みのようなイメージに近くなってきました。１つだけ固定されてあと全部抜けたみたいな。それがぶらりと振り子のように揺れているイメージです。どうでしょうか。