![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67b6d)
グラフ構造のアルゴリズムの問題です。
頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか?
何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。
以下、問題文です。
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ベストアンサー
- 回答日時:
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.2
- 回答日時:
「重みの制限」ってのは, 主に「負の重みは許されているのか」ってところで問題になりうるんで確認してみました. もちろん, 整数だけなのかそれとも任意の実数が許されるのかによっても難しさ (というか面倒くささ) が違う可能性もあるんだけど.
で「元のグラフを復元できるかどうか」ですが.... もちろん完全な復元はできませんが, 「ここに挙がっている数値と矛盾のないようなグラフ」は作れる可能性があります. 例えば, 距離が ∞ になっているような 2頂点は隣接していないことが確定します. さらに, 「v1~v6 でできる誘導部分グラフ」においては
・v4 は他のいずれの頂点とも連結していない
・vi から vj への最短路は「(隣接していれば) 直接行く」ルートか「vi から vk への最短路に vk から vj への最短路をつないだ」ルートかのいずれか
なので, これらの情報を駆使することでグラフが作れるかもしれません.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・「I love you」 をかっこよく翻訳してみてください
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・昔のあなたへのアドバイス
- ・かっこよく答えてください!!
- ・あなたが好きな本屋さんを教えてください
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
aは正の定数とする。関数y=x²...
-
y=-x^2+2x+3の平方完成について...
-
数学の問題
-
2次関数y=x^2-2ax+2a^2-5のグラ...
-
定義域と値域の求め方
-
3次関数
-
【至急】 x²-(a-3)x+2a+4=0が正...
-
0≦x≦8のすべてのxについて、不...
-
青チャートの問題ですが
-
y=ax^2+bx+cにおいて、a,b,cの...
-
エクセルで三次関数をつくりた...
-
【平方完成の問題です。 次の2...
-
高校 数学
-
数学1 二次関数 y=x^4+4x^3+5x...
-
(2)からわかりません、。 途中...
-
二次関数X2-4X+5がある。(X2はX...
-
-2(x-2)²+4の軸と頂点を教えて...
-
グラフ構造のアルゴリズムの問...
-
二次方程式の解の書き方
-
恒等的に正しいとはどういう意...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
aは正の定数とする。関数y=x²...
-
高校数学の問題の解説をお願い...
-
【至急】 x²-(a-3)x+2a+4=0が正...
-
平方完成のやり方を教えてくだ...
-
数学I y=x^2-2ax+aのグラフとx...
-
数Ⅰを教えて欲しいです。 問、a...
-
次の条件が成り立つような定数a...
-
0≦x≦8のすべてのxについて、不...
-
不等式で表される領域が分かり...
-
y=ax^2+bx+cにおいて、a,b,cの...
-
3次関数
-
(2)でなぜ二次関数のグラフが...
-
-2(x-2)²+4の軸と頂点を教えて...
-
数学の問題
-
青チャートの問題ですが
-
2次関数y=(x+2)2乗-3の最大...
-
数学1 二次関数 y=x^4+4x^3+5x...
-
数学1 二次関数 不等号 イコー...
-
Y=x2乗+2x+3の頂点と対称軸...
-
3次関数y=x^3-2ax^2+a^2x (a>0)...
おすすめ情報