• ベストアンサー

ベルマンフォードのアルゴリズム

このカテゴリーであってる・・・かな・・。 とりあえず、ネットワークのアルゴリズムなので。 最短経路を求めるアルゴリズムは、 ダイクストラしか知らなかったのですが、 ベルマンフォードというアルゴリズムがあると知りました。 どのようなアルゴリズムなのでしょうか？ ダイクストラと比較してどうなのでしょうか？

noname#6448
noname#6448

質問者が選んだベストアンサー

  • ベストアンサー
回答No.1

参考になるページがこちらに http://www.threeweb.ad.jp/~makita/short2.html http://premium.mag2.com/sample/P0000264.html さらにドキュメントを探すと http://www.google.co.jp/search?hl=ja&ie=UTF-8&oe=UTF-8&q=Bellman-Ford+routing&btnG=Google+%E6%A4%9C%E7%B4%A2&lr= 等があります。

noname#6448
質問者

お礼

ありがとうございます。。 リンクをみてみましたが、なかなかおもしろいですね。 勉強しとこう。。 ありがとうございました

  1. カテゴリ
  2. インターネット・Webサービス
  3. インターネット接続・通信
  4. その他（インターネット接続・通信）

関連するQ&A

  • 最短経路問題のアルゴリズム

    最短経路問題のアルゴリズムにはどのようなものがありますか？ ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。

  • 任意の2地点間の全経路探索について

    ネットワーク上においてダイクストラ法を使うと任意の２地点間の最短経路が求められますが、最短経路だけでなく最長経路など任意の２地点間における全ての経路を求めたいと考えていますが、なかなか良いアルゴリズムができません。詳しい方御教授お願いいたします。

  • ルーティングプロトコルの実装

    アドホックネットワークのルーティングプロトコルのプログラムをCで作成し、 ダイクストラの経路選択法を用いてサーバまでの最短経路を求めています。 　　　　／[端末A]－・・＼ [サーバ]　　　　　　　　　[クライアント] 　　　　＼[端末B]－・・／ 最短経路以外の予備経路も保持したいのですが、ダイクストラ法では 最短経路しか保持しないので困っています。第一経路＋第二経路　を作りたいのですが・・ よい案がないか、どなたかご指南いただけないでしょうか。

  • グラフ理論について

    最短経路選択手法としてダイクストラ法があります。 エッジに重みを与え、始点から終点までの最短経路を算出する手法ですが、この時ノードの重みは考慮されません。 ここで質問です。 ノードの重みも考慮するアルゴリズムはあるのでしょうか？ 詳しい方、ご教授お願いします。

  • 最短経路のアルゴリズム

    このジャンルでお願いします。 左下の座標を(1,1)として ○(4,4)が△(7,2)に辿りつく最短経路のアルゴリズムが知りたいです。 ■は通れない場所です。 □□□□□□□ □□■■□□□ □□□□■□□ □■□○■□□ □■□■■□□ □□■□□△□ □□□□□□□ ↑ (1,1)

  • A*アルゴリズムとダイクストラ法について

    A*アルゴリズムとダイクストラ法について質問です。 (1)A*アルゴリズムは万能のように思えるのですが、どのようなデメリットがありますか？ (2)ダイクストラ法がA*より優れている点はありますか？ A*アルゴリズムを調べてみたのですが主なデメリットは見つけられなかったので疑問に思いました。 回答よろしくお願いします

  • A*アルゴリズム

    授業のレポート課題で「A*アルゴリズムは最短経路問題を見出すことを証明せよ」とゆう問題が出ました。図書館とかネットを調べましたがわかりません。誰かわかる人がいたら教えてください！

  • ダイクストラ法

    ふと思ったのですが、 最短経路問題を解くときに使用されるダイクストラ法ってありますが。 このダイクストラ法で解けない問題ってありますか？

  • 最短距離を求める問題（ダイクストラ法）の原理

    グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。

  • プログラム仕様について

    ダイクストラを用いて最短経路探索のプログラムをＪＡＶＡで作ろうとしているのですが、肝心なプログラム仕様書及びフローチャートが書けません。 どなたかお力おかしください

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する