グラフ構造のアルゴリズムの問題です。
頂点間の最短距離を求める問題ですが、どうすれば良いかわかりません......。ダイクストラ法などを使うのでしょうか?
何のアルゴリズムを利用するのかという点と、解法の手順を解説していただけると幸いです。
以下、問題文です。
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で質問しましょう!
似たような質問が見つかりました
- Excel(エクセル) エクセルの印刷マクロについて質問があります。 現在、下記のマクロで印刷しています。Sheet1のD6 5 2023/06/12 10:59
- Excel(エクセル) 文字列を数式として変換する事はできますか? 6 2022/06/23 10:38
- その他(パソコン・スマホ・電化製品) 小さめのモニタースピーカー探しで悩んでいます。 2 2022/05/26 12:40
- ビデオカード・サウンドカード グラボ増設 3 2022/07/28 09:15
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
- Visual Basic(VBA) ExcelVBAで、型が一致しませんのエラーについて 3 2023/06/20 09:51
- その他(Microsoft Office) googleスプレットシートで左右の数値を比較して色判別させたい 2 2022/06/06 18:33
- Visual Basic(VBA) Excel VBA メール作成について 本文の中にExcel でコピーした図を上下に2つ 貼り付けを 2 2023/06/14 01:48
- Visual Basic(VBA) ExcelVBAでDo Until loopのネスト、IF文を使って一致する物と一致しない物としたい 11 2022/12/24 17:46
- Excel(エクセル) エクセル2019の関数を教えてください。 8 2022/12/16 12:45
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
(2)でなぜ二次関数のグラフが...
-
xy=k
-
不等式はたすきがけ?平方完成
-
次の条件が成り立つような定数a...
-
数学1 二次関数 y=x^4+4x^3+5x...
-
青チャートの問題ですが
-
(数B、数列) (2)でこのような解...
-
数学の問題です f(x)=ax^2−4αx...
-
【至急】 x²-(a-3)x+2a+4=0が正...
-
高校数学の問題の解説をお願い...
-
数学 3次関数
-
こちらの式はtan(z)のローラン...
-
2024.4.7 03:42の質問に対する2...
-
e^iθの大きさ
-
sin(ωt+θ) のラプラス変換
-
SPIの問題
-
画像のように、マイナスをsinの...
-
位相差を時間に
-
高1 数学 sin cos tan の場所っ...
-
cosx/sinxの積分を教えてください
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
-2(x-2)²+4の軸と頂点を教えて...
-
aは正の定数とする。関数y=x²...
-
高校の数学で、極大値と最大値...
-
高校数学の問題の解説をお願い...
-
y=-x^2+2x+3の平方完成について...
-
【至急】 x²-(a-3)x+2a+4=0が正...
-
平方完成のやり方を教えてくだ...
-
数学1 二次関数 不等号 イコー...
-
不等式で表される領域が分かり...
-
y=ax^2+bx+cにおいて、a,b,cの...
-
数学のご質問
-
3次関数
-
高校数学 二次関数の最小値(絶...
-
数学1 二次関数 y=x^4+4x^3+5x...
-
上に凸の条件
-
高一の『確率』など(コツを)
-
ax+byの最大値、最小値をグラフ...
-
数Ⅰを教えて欲しいです。 問、a...
-
2次関数y=(x+2)2乗-3の最大...
-
定義域と値域の求め方
おすすめ情報