グラフ構造のアルゴリズムの問題です。
グラフ構造のアルゴリズムの問題です。
頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか？
何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。
以下、問題文です。
v1,v2,v3,..., v9,v10 の 10 個の頂点からなる重みつき無向グラフ G の全頂点間の最短距離を計算したい。こ こで dk(i,j) を頂点 vi から頂点 vj への「経由してよい頂点を v1,...,vk に限定した」最短距離とする。例えば, d3(i,j)は「経由してよい頂点が v1,v2,v3 に限定された」vi から vj への最短距離となる。
ただし,v1,...,vk までの頂点のみを経由するような vi から vj への経路がない場合は dk(i,j)を∞とする。
いま,「経由してよい頂点を v1～v6 に限定した」全頂点間の最短距離がそれぞれ
d6(1,2)=3 d6(1,3)=12 d6(1,4)=∞ d6(1,5)=4 d6(1,6)=6 d6(1,7)=∞ d6(1,8)=4 d6(1,9)=8 d6(1,10)=9 d6(2,3)=5 d6(2,4)=∞ d6(2,5)=2 d6(2,6)=3 d6(2,7)=∞ d6(2,8)=1 d6(2,9)=6 d6(2,10)=3
d6(3,4)=∞ d6(3,5)=5 d6(3,6)=2 d6(3,7)=∞ d6(3,8)=6 d6(3,9)=9 d6(3,10)=5
d6(4,5)=∞ d6(4,6)=∞ d6(4,7)=2 d6(4,8)=∞ d6(4,9)=∞ d6(4,10)=4
d6(5,6)=5 d6(5,7)=∞ d6(5,8)=3 d6(5,9)=4 d6(5,10)=8
d6(6,7)=∞ d6(6,8)=4 d6(6,9)=9 d6(6,10)=3
d6(7,8)=3 d6(7,9)=∞ d6(7,10)=1
d6(8,9)=4 d6(8,10)=7
d6(9,10)=12
であった。この情報をもとに以下のそれぞれの値を求めよ。
(1)d7(1,10)
(2)d7(4,8)
(3)d7(4,10)
(4)d8(1,10)
(5)d8(4,5)
お手数お欠けしますが、どうかよろしくお願い致します。
お礼
ありがとうございました。
補足
学習を進めていったところ、私も（１）は部分木だと思いました。 （２）はオイラーグラフかと思います。