20/01/15 23:25:41 Ex9G0OLU.net
>>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
1000:デフォルトの名無しさん
20/01/15 23:28:15 Ex9G0OLU.net
URLﾘﾝｸ(www.geeksforgeeks.org)
これとかわりとそのままだな 重みなしだけど
1001:デフォルトの名無しさん
20/01/15 23:56:14 Ex9G0OLU.net
URLﾘﾝｸ(www.geeksforgeeks.org)
こっちは重み付きのやつ
1002:デフォルトの名無しさん
20/01/18 22:58:37.26 iLU56BHo.net
>>983
>>984
ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。
1003:デフォルトの名無しさん
20/01/19 12:55:00.98 VFlG/sWR.net
CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
1004:デフォルトの名無しさん
20/01/20 15:11:46.01 +ZQhvd/Y.net
巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね
1005:デフォルトの名無しさん
20/01/20 17:27:30.27 /b+J8VIk.net
>>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
1006:デフォルトの名無しさん
20/01/20 17:28:22.60 /b+J8VIk.net
途中で送信してしまった
このときの経路をvetorにいれておけばいい
1007:デフォルトの名無しさん
20/01/25 23:49:17 Q85YRMjK.net
>>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。
厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。
悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。
1008:デフォルトの名無しさん
20/01/26 01:32:16.02 63DOpTVc.net
言語の基本的な部分はさすがによそでやろうや・・・
1009:デフォルトの名無しさん
20/01/26 13:25:18.52 eN1PAkvI.net
>>990
URLﾘﾝｸ(ideone.com)
↑一応動きました。
piという変数に経路を覚えさせています。
1010:デフォルトの名無しさん
20/01/26 13:32:46.65 eN1PAkvI.net
>>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
1011:デフォルトの名無しさん
20/01/26 13:47:50.10 eN1PAkvI.net
アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？
1012:デフォルトの名無しさん
20/01/26 16:03:48.66 gJO14xRt.net
>>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い
1013:デフォルトの名無しさん
20/01/26 16:28:11 eN1PAkvI.net
>>995
ありがとうございます。
機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。
1014:デフォルトの名無しさん
20/01/27 12:15:36 Dkceayzl.net
DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
1015:デフォルトの名無しさん
20/01/27 17:15:29 Xu7tzl7q.net
>>996
+1
1016:デフォルトの名無しさん
20/01/27 17:16:05 Xu7tzl7q.net
>>997
-1
1017:デフォルトの名無しさん
20/01/27 17:16:23 Xu7tzl7q.net
>>999
+1=1000
1018:1001
Over 1000 Thread .net
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
1019:過去ログ ★
[過去ログ]
■ このスレッドは過去ログ倉庫に格納されています