グラフ構造のアルゴリズムの問題です。

質問

グラフ構造のアルゴリズムの問題です。
頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか？
何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。

以下、問題文です。

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)

お手数お欠けしますが、どうかよろしくお願い致します。

回答No.7

MagicianKuma · ベストアンサー

dk+1(i,j)とdk(i,j)の違いを考えると寄り道できる制約がvk+1の点だけ緩くなったわけです。なので少なくともdk+1(i,j)≦dk(i,j)が成立する。
viからvjに行く間にvk＋1を通った場合の最短距離はdk(i,k+1)+dk(k+1,j)。ゆえにdk+1(i,j)=min(dk(i,j),dk(i,k+1)+dk(k+1,j))となる。この左辺が与えられていればdk+1(i,j)が求まる。 以上。勘違いしてるかな？

お礼

なるほど！すごくすっきりわかりました！！
ありがとうございました！！

回答No.6

Tacosan

あ, 本当だ. それは気づかなかった＞#5.

回答No.5

MagicianKuma

問題が変ではないかい？ d6(1,2)=3でd6(2,3)=5ならv1からv3への最短は8以下になるはず。なのにd6(1,3)=12？？？

回答No.4

Tacosan

そんな感じです.

お礼

わかってきました。ありがとうございます！！

回答No.3

Tacosan

ごめん, ちょっと考えたらそこにある数値をそのまま辺の重みにしていいような気がしてきた.

補足

もしかしたら、d7(1,10) = d6(1,10) or d6(1,7)+d6(7,10)
みたいな感じになりませんか？？そういうことですかね？

回答No.2

Tacosan

「重みの制限」ってのは, 主に「負の重みは許されているのか」ってところで問題になりうるんで確認してみました. もちろん, 整数だけなのかそれとも任意の実数が許されるのかによっても難しさ (というか面倒くささ) が違う可能性もあるんだけど.

で「元のグラフを復元できるかどうか」ですが.... もちろん完全な復元はできませんが, 「ここに挙がっている数値と矛盾のないようなグラフ」は作れる可能性があります. 例えば, 距離が ∞ になっているような 2頂点は隣接していないことが確定します. さらに, 「v1～v6 でできる誘導部分グラフ」においては
・v4 は他のいずれの頂点とも連結していない
・vi から vj への最短路は「(隣接していれば) 直接行く」ルートか「vi から vk への最短路に vk から vj への最短路をつないだ」ルートかのいずれか
なので, これらの情報を駆使することでグラフが作れるかもしれません.

回答No.1

Tacosan

「お手数お欠けしますが」ってどういうことだろう.

「元のグラフを復元しろ」ってことかなぁ.... とりあえず v1～v6 についてはグラフが作れそうだけど....

あ, 重みに制限はありますか?

補足

すみません....誤字に気付きませんでした。
重みに制限はないです。
元のグラフを復元するって、与えられた最短経路の情報は途中どの経路を通ったかわからないのに、できるんですか？