5つの状態 a, b, c, d, eを持つシステムにおける状態間の遷移と遷移コストが与えられています。 問題は以下の2つです。 1. 初期状態 $s_1$ を追加し、$s_1$ から a への遷移コストが 3、$s_1$ から d への遷移コストが 2 であるとき、$s_1$ から e への最短路とそのコストを求めます。

1. 問題の内容

5つの状態 a, b, c, d, eを持つシステムにおける状態間の遷移と遷移コストが与えられています。

問題は以下の2つです。

1. 初期状態 $s_1$ を追加し、$s_1$ から a への遷移コストが 3、$s_1$ から d への遷移コストが 2 であるとき、$s_1$ から e への最短路とそのコストを求めます。

2. 初期状態 $s_2$ を追加し、$s_2$ から b への遷移コストが 6、$s_2$ から c への遷移コストが 1 であるとき、ダイクストラ法を用いて最短路木を求めます。

2. 解き方の手順

(1) $s_1$ から e への最短路の探索

まず、与えられた遷移関係とコストを整理します。

* $a \leftrightarrow b$: 4

* $b \leftrightarrow e$: 8

* $c \rightarrow a$: 1

* $b \rightarrow d$: 3

* $c \rightarrow e$: 6

* $d \rightarrow a$: 2

* $s_1 \rightarrow a$: 3

* $s_1 \rightarrow d$: 2

考えられる経路を列挙し、コストを計算します。

* $s_1 \rightarrow a \rightarrow b \rightarrow e$: $3 + 4 + 8 = 15$

* $s_1 \rightarrow d \rightarrow a \rightarrow b \rightarrow e$: $2 + 2 + 4 + 8 = 16$

* $s_1 \rightarrow d \rightarrow a \leftrightarrow b \rightarrow e$: $2+2+4+8=16$

* $s_1 \rightarrow d \rightarrow a \rightarrow b \rightarrow d$: $2 + 2 + 4 + 3 = 11$ (この場合 $d$ から $e$ に直接遷移できないため、これは正しい経路ではありません。)

$s_1$ から $d$ に行き、$d$ から $a$ に行き、$a$ から $b$ に行き、$b$から$e$に行く経路があることがわかりました。

$s_1 \rightarrow d \rightarrow a \rightarrow b \rightarrow e$ のコストは 16

$s_1$から$a$に直接行き、$a$から$b$に直接行き、$b$から$e$に直接行く経路があることがわかりました。

$s_1 \rightarrow a \rightarrow b \rightarrow e$ のコストは 15

次に、$s_1$からeに直接行く経路がないか調べます。直接行く経路がないため、他のノードを経由する必要があります。

$s_1 \rightarrow d \rightarrow a \rightarrow b \rightarrow e$ と $s_1 \rightarrow a \rightarrow b \rightarrow e$ のどちらがコストが低いかを比較します。

経路 $s_1 \rightarrow a \rightarrow b \rightarrow e$ のコストは、$3+4+8 = 15$ です。

経路 $s_1 \rightarrow d \rightarrow a \rightarrow b \rightarrow e$ のコストは、$2 + 2 + 4 + 8 = 16$ です。

したがって、$s_1$ から e への最短路は $s_1 \rightarrow a \rightarrow b \rightarrow e$ であり、そのコストは 15 です。

(2) ダイクストラ法による最短路木の構築

$s_2$ を始点として、ダイクストラ法を適用します。状態は $s_2$, a, b, c, d, e です。

$s_2$ からの遷移コストは以下の通りです。

* $s_2 \rightarrow b$: 6

* $s_2 \rightarrow c$: 1

他の遷移コストは問題文に記載されています。

ダイクストラ法の各ステップにおける状態ごとの最小コストと、直前のノードは以下のようになります。

初期状態:

* $s_2$: 0, -

* a: $\infty$, -

* b: $\infty$, -

* c: $\infty$, -

* d: $\infty$, -

* e: $\infty$, -

1. $s_2$ を選択:

* b: 6, $s_2$

* c: 1, $s_2$

2. c を選択:

* a: 2, c (c->a:1なので、1+1=2)

* e: 7, c (c->e:6なので、1+6=7)

3. a を選択:

* b: 6, $s_2$ （既存の値より大きいので更新しない。）

4. b を選択:

* d: 9, b (6+3=9)

* e: 14, b (6+8=14)

5. d を選択:

* a: 11, d （既存の値より大きいので更新しない。）

6. e を選択:

最終的な最小コストは以下の通りです。

* $s_2$: 0

* a: 2, c

* b: 6, $s_2$

* c: 1, $s_2$

* d: 9, b

* e: 7, c

したがって、最短路木は以下のようになります。

* $s_2 \rightarrow b$

* $s_2 \rightarrow c$

* $c \rightarrow a$

* $b \rightarrow d$

* $c \rightarrow e$

3. 最終的な答え

(1) $s_1$ から e への最短路は $s_1 \rightarrow a \rightarrow b \rightarrow e$ であり、そのコストは 15 です。

(2) ダイクストラ法による最短路木は以下の通りです。

* $s_2 \rightarrow b$

* $s_2 \rightarrow c$

* $c \rightarrow a$

* $b \rightarrow d$

* $c \rightarrow e$