掲示板システム
ホーム
アクセス解析
カテゴリ
ログアウト
初歩的なグラフの問題 (ID:72943)
名前
ホームページ(ブログ、Twitterなど)のURL (省略可)
本文
逆に聞く形になってしまいますが，私が調べた感じ ベルマンフォード法は以下のようなアルゴリズムという認識ですがこれでＯＫでしょうか？ （便宜上，処理単位を"Turn"と記し，ノード個数をNとする） [開始処理] ・開始点への到達コストを0に（更新）する ・その他のノードの到達コストは∞としておく ・Turn=0 [各Turnでの処理] ・前Turnで到達コストが更新されたノード群について，隣接ノードへの到達コストを計算． それが，既存の結果よりも小さいコストであれば，隣接ノードの到達コストを更新する ・Turn++ ・if( Turn>=N )終了処理へ else ループ [終了処理] ・もし，未だに更新が可能な個所が残っているならば， それは負の閉路に捕らわれた探索個所が残っているのであり， ”最短経路はない”が答えとなる． ・負の閉路が存在しないならば，この時点で答えが求まっている アルゴリズムがこれで合っているならば，おっしゃる通り， 更新していく情報に「通ったノード群」を追加してやればいけそうに思います． ＃メール到達失敗の件は了解しました． （ということは，現在，メールは使用不可ということなのかな？）
←解決時は質問者本人がここをチェックしてください。
更新する
戻る
掲示板システム
Copyright 2021 Takeshi Okamoto All Rights Reserved.