- 締切済み
ダイクストラ法の計算量の求め方を知ってらっしゃる方いますか?
- みんなの回答 (2)
- 専門家の回答
みんなの回答
- loadidentity
- ベストアンサー率66% (6/9)
ここにソースが載ってます。 参考になるといいですね。 http://www-or.amp.i.kyoto-u.ac.jp/members/ibaraki/algo.shtml
- toysmith
- ベストアンサー率37% (570/1525)
これですか? アルゴリズム辞典で調べた方が詳しいかもしれません。
関連するQ&A
- ダイクストラ(dijkstra)法のソース
現在C言語初めて1週間です。 ダイクストラ法について調べています。 WEB検索をかけると沢山ヒットするのですが、 ソースがわかりにくいのが多くて困っています。 アルゴリズムからわかりやすく紹介されているサイトを教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- ダイクストラ法の実行時間
ダイクストラ法の実行時間が, O(n)なのは様々なサイトを見ていると分かるのですが, なぜ,O(n^2)なのかが分かりません. それと,ヒープを使った際に, O((n+m)log(n))になる理由がわかりません. どなたか,分かりやすい解説をお願いします.
- ベストアンサー
- 情報処理技術者
- 文字列探索KMP法の計算量について。
KMP法の計算量についての質問です。 (1)計算量がO(M+N)になるのは何故か? (2)この計算量は漸近的には改善できない最善のものであると記載されているが、それは何故か? ※テキストの長さ=N、キー(パターン)の長さ=M 参考書を見て勉強していたのですが、計算量については省略されてしまっていたために不明なままです。どなたかご存知の方がいらっしゃいましたらよろしくお願いします。
- ベストアンサー
- C・C++・C#
- Dijkstra法のデータ構造による計算量の変化
Dijkstra法を実行するプログラムを隣接行列と隣接リストを用いてそれぞれ実装しました。 そこでデータ構造の違いによる計算量の違いをオーダー表記を用いて表そうとしているのですが どのように計算すればいいのか検討がつきません。 次の点に行くためにどのような処理が必要か、また点を訪れてからどのような処理が必要かを求めれば良いみたいです。 回答よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 最短距離を求める問題(ダイクストラ法)の原理
グラフ(経路)の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。
- 締切済み
- C・C++・C#