質問: グラフ構造のアルゴリズムの問題です。 グラフ構造のアルゴリズムの問題です。 頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか? 何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。 以下、問題文です。 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) お手数お欠けしますが、どうかよろしくお願い致します。
回答: 「重みの制限」ってのは, 主に「負の重みは許されているのか」ってところで問題になりうるんで確認してみました. もちろん, 整数だけなのかそれとも任意の実数が許されるのかによっても難しさ (というか面倒くささ) が違う可能性もあるんだけど. で「元のグラフを復元できるかどうか」ですが.... もちろん完全な復元はできませんが, 「ここに挙がっている数値と矛盾のないようなグラフ」は作れる可能性があります. 例えば, 距離が ∞ になっているような 2頂点は隣接していないことが確定します. さらに, 「v1~v6 でできる誘導部分グラフ」においては ・v4 は他のいずれの頂点とも連結していない ・vi から vj への最短路は「(隣接していれば) 直接行く」ルートか「vi から vk への最短路に vk から vj への最短路をつないだ」ルートかのいずれか なので, これらの情報を駆使することでグラフが作れるかもしれません.