• 締切済み

ダイクストラ法

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

  • 科学
  • 回答数1
  • ありがとう数0

みんなの回答

  • sunasearch
  • ベストアンサー率35% (632/1788)
回答No.1

基本的に全探索ですから、解けます。 普通でない、解けない例としては、 ・枝の数が多くて、死ぬまでに計算が終わらない ・距離がマイナスの値を取る ・枝の距離が通ってきた道筋によって変化する などです。

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 科学

関連するQ&A

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

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

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

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

  • フィボナッチヒープです

    今、ダイクストラ法を用いて最短経路問題についてのプログラムを作成して完成したところです. このダイクストラ法をフィボナッチヒープを用いて高速化できると聞きました. ウィキペディァで見てもよくわかりません。。。。 どなたか、このフィボナッチヒープの仕組みなど解説しているサイトを教えて下さい. できたら、この場での解説もお願いします.

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

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

  • ダイクストラ法　隣接リスト

    ダイクストラ法をC言語で隣接配列で書くことができたんですけど隣接リストでの書き方がわかりません。 まずデータ構造をどのようにすればいいですか？

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

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

  • ダイクストラ(dijkstra)法のソース

    現在Ｃ言語初めて１週間です。 ダイクストラ法について調べています。 WEB検索をかけると沢山ヒットするのですが、 ソースがわかりにくいのが多くて困っています。 アルゴリズムからわかりやすく紹介されているサイトを教えてください。 よろしくお願いします。

  • グラフ理論について

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

  • ダイクストラ法の実行時間

    ダイクストラ法の実行時間が， O(n)なのは様々なサイトを見ていると分かるのですが， なぜ，O(n^2)なのかが分かりません． それと，ヒープを使った際に， O((n+m)log(n))になる理由がわかりません． どなたか，分かりやすい解説をお願いします．

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

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

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する