どのようなアルゴリズムになるか教えてください！！ お願いします！！！！ 見えにくいでしょうか。、

どのようなアルゴリズムになるか教えてください！！
お願いします！！！！

見えにくいでしょうか。、

No.2 ベストアンサー 回答者： stomachman 回答日時： 2018/11/26 17:38

問題の文脈がよくわからんけれど、最短路を問う以上は、おそらく各arc (edge) aに何らか重みw(a)が対応づけられていて、かつ、どの重みw(a)も正の実数である、という話なのだろう。

また、この場合に最短路木と呼んでいる木は、Gの全てのvertexを要素とするグラフであろう。
　注意すべきは、最短路木を作るよう求めているのではなく、与た最短路木の検証(verification)を求めている、というところ。すなわち、
(1) その木によって決まる、vertex vのrootからの距離dを、全てのvertexについて計算したものを d(v) (v∈V) とする。特に, d(root) = 0。
(2) それぞれのvertex vについて、vに入ってくるarc a の集合をA(v)、そのarc aの出発点のvertexをf(a)とする。 すべての vertex v∈Vについて、
　　d(v) = min { d(f(a)) + w(a) | a∈A(v) }
を確かめれば「与えられた木は最短路木だと思っても矛盾しない」と言えて、このとき、与えられた木が最短路木になってる。（「なってると言える」ということ自体は数学的証明を要するが。）
　すると、(1)と(2)の処理をそれぞれ、すでに与えられている木に沿った深さ優先探索でやれば良い。
　（特にw がすべて1という場合なら、木に沿った幅優先探索でやれば(1)と(2)を同時に処理できるだろうに、深さ優先でやれというのだから、wはイロイロなのだろう。）
…という話なのかしらん？それとも、f(a)が簡単には計算できない、という条件が付いているのかしらん？

この回答へのお礼

そういうことです！！！！
ありがとうございます！！！れ

お礼日時：2018/11/28 10:15

No.3 回答者： Tacosan 回答日時： 2018/11/27 00:13

s から他の頂点までの最短距離を全部計算してしまえば, T が最短路木かどうかは簡単にわかる.

No.1 回答者： toku4de-su 回答日時： 2018/11/25 17:46

最短経路木の問題ですよね。

私は、工学修士を持っていますが、授業でやった記憶がありますが、忘れてしまいました。

教えて!goo >教育・科学・学問 >応用科学 >工学

で、再度質問されてはいかがでしょう。

この回答へのお礼

ありがとうございます！
参考にします！

お礼日時：2018/11/25 20:34