Dijkstra法

質問

大学２年生です。
教えてください。

有向ネットワークN=(V,E,d)におけるDijkstra法に関して以下の問いに答えなさい。

1、Dijkstra法は、（Nの他に）『何を指定されて何を計算する』アルゴリズムか。

2、Dijkstra法が正しく働くために。枝の長さd=(dij)はどのような条件を満たさなければならないか。

3、Dijkstra法は、アルゴリズムの実行過程で、Vの各点に数値（ラベル値）をつけ、それを更新して行く。実行の各段階におけるラベル値の性質によって、Vは2つの集合S１、S２に分割される。どのような性質によって分割されるのか述べなさい。

４、実行の各段階で、S２の要素１個が、S１に移される。どのような要素がS２からS１へ移されるのか。

５、４の操作が有効であるように、S２に属する点のラベル値はある性質（S１に属する点のラベル値達との間のしかるべき関係）を満たすよう保たれる。その関係式を示しなさい。

回答No.3

kyohei-m

一緒に単位取ろうね。

回答No.2

noname#221368

ダイクストラ法って本当に、普通の事しかやってないんですよ。

　ある一点から出発して、1点から到達できる各ステップにおける全て通過履歴の中で、道なりの距離最小（あるいは時間距離最小）を選び続けていれば、目的点を含むステップに達した時に、自然に距離最小（あるいは時間距離最小）なルートを選択した事になる、という話です。

　余りにも当たり前の話ですが、本当の総当たり（多分木検索）と比較すると、経験上1000倍以上効率が良いです。このような方法こそ、価値があると思えます。

　しかし、いざ数学的に証明しようと思うと、あまりにも当然（数学的トリックやショートカットは皆無）なので、逆に戸惑います。道路ネットワークの各種手法は、そんなのばっかりです。そこで見通しを少しでも良くしようとして、道路ネットワークという系を論理的に整理して「定義」しようとします。

　これもまた「当たり前」の事を「面倒くさく」言っただけなので、逆に災いになったりするのですが言いたいことは、上から下まで当たり前の事を当たり前に述べただけなので、地道に読めば「必ずわかります」という事です。

　件が当たり前過ぎるので、逆に説明に窮するみたいな感じです(^^；)。やれば出来ます(^^)。

回答No.1

kmee

1,2くらいは自分で調べましょう。
教科書、参考書等、図書館とかで調べれば簡単にわかります。
Googleで「Dijkstra法」で検索して、上から順番に読んでいけば、答えがわかります。
ここに質問をコピペして回答を待つ、という無駄な時間を過したことになります。

卒論とかになったら、そういう調べものばかりです。
今から慣れておきましょう