ネットワークと各種グラフ問題ネットワークとその問題重み付きグラフ全ての路とコスト

学習環境

情報系のための離散数学 (猪股俊光 (著)、南野謙一 (著)、共立出版)の第9章(ネットワークと各種グラフ問題)、9.1(ネットワークとその問題)、9.1.1(重み付きグラフ)、問9.1の解答を求めてみる。

路

P : a, b, c, d

のコスト。

200 + 240 + 100 = 540

\begin{array}{l} a, b, e, d \\ 200 + 200 + 300 = 700 \end{array}

\begin{array}{l} a, f, e, b, c, d \\ 150 + 180 + 200 + 240 + 100 = 870 \end{array}

\begin{array}{l} a, f, e, d \\ 150 + 180 + 300 = 630 \end{array}