• 締切済み

ダイクストラ法の計算量の求め方を知ってらっしゃる方いますか?

ダイクストラ法の計算量の求め方を知ってらっしゃる方いますか? できれば、ダイクストラ法のプログラムも教えてください。

みんなの回答

回答No.2

ここにソースが載ってます。 参考になるといいですね。 http://www-or.amp.i.kyoto-u.ac.jp/members/ibaraki/algo.shtml

  • toysmith
  • ベストアンサー率37% (570/1525)
回答No.1

これですか? アルゴリズム辞典で調べた方が詳しいかもしれません。

参考URL:
http://www.yilab.tutics.tut.ac.jp/aki/ZEMI/dijkstra.html

関連するQ&A

  • ダイクストラ法

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

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

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

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

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

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

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

  • 計算量について

    プログラムの計算量について質問です。計算量には時間計算量と空間計算量がありますが、そのうち空間計算量の概念がいまいち分かりません。アルゴリズムが必要とする記憶容量といっても漠然としててどのように求めたらいいのか分かりません。 例えばプログラムの基本構成が for(n回){ for(n回){ 処理 } } のようだったら時間計算量がO(n^2)というのはわかるんですが、この場合の空間計算量はどのようになりますか?

  • 文字列探索KMP法の計算量について。

    KMP法の計算量についての質問です。 (1)計算量がO(M+N)になるのは何故か? (2)この計算量は漸近的には改善できない最善のものであると記載されているが、それは何故か? ※テキストの長さ=N、キー(パターン)の長さ=M 参考書を見て勉強していたのですが、計算量については省略されてしまっていたために不明なままです。どなたかご存知の方がいらっしゃいましたらよろしくお願いします。

  • Dijkstra法のデータ構造による計算量の変化

    Dijkstra法を実行するプログラムを隣接行列と隣接リストを用いてそれぞれ実装しました。 そこでデータ構造の違いによる計算量の違いをオーダー表記を用いて表そうとしているのですが どのように計算すればいいのか検討がつきません。 次の点に行くためにどのような処理が必要か、また点を訪れてからどのような処理が必要かを求めれば良いみたいです。 回答よろしくお願いします。

  • ダイクストラとかけまして、麻雀ととく、その心は?

    ダイクストラとかけまして、麻雀ととく、その心は?面白い答えをお待ちしています.

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

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

  • 計算量

    記憶計算量と時間計算量の求め方がいまいちよくわかりません。どなたか教えてください。