kyohei-mのプロフィール

大学２年生です。 教えてください。 有向ネットワーク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１に属する点のラベル値達との間のしかるべき関係）を満たすよう保たれる。その関係式を示しなさい。