- ベストアンサー
フィボナッチヒープです
今、ダイクストラ法を用いて最短経路問題についてのプログラムを作成して完成したところです. このダイクストラ法をフィボナッチヒープを用いて高速化できると聞きました. ウィキペディァで見てもよくわかりません。。。。 どなたか、このフィボナッチヒープの仕組みなど解説しているサイトを教えて下さい. できたら、この場での解説もお願いします.
- C・C++・C#
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
関連するQ&A
- ルーティングプロトコルの実装
アドホックネットワークのルーティングプロトコルのプログラムをCで作成し、 ダイクストラの経路選択法を用いてサーバまでの最短経路を求めています。 ／[端末A]－・・＼ [サーバ] [クライアント] ＼[端末B]－・・／ 最短経路以外の予備経路も保持したいのですが、ダイクストラ法では 最短経路しか保持しないので困っています。第一経路＋第二経路 を作りたいのですが・・ よい案がないか、どなたかご指南いただけないでしょうか。
- ベストアンサー
- C・C++・C#
- プログラム仕様について
ダイクストラを用いて最短経路探索のプログラムをＪＡＶＡで作ろうとしているのですが、肝心なプログラム仕様書及びフローチャートが書けません。 どなたかお力おかしください
- 締切済み
- その他([技術者向] コンピューター)
- 最短経路表示の追加プログラム
下のリンク先のプログラムはダイクストラを用いた最短”距離”を求めるプログラム何ですが、このプログラムに最短距離の最短”経路”を表示する追加のプログラムを求めているんでけど、よろしければお答えしてもらえませんか？http://www.nda.ac.jp/~yamada/programs/programs.html
- 締切済み
- C・C++・C#
- 任意の2地点間の全経路探索について
ネットワーク上においてダイクストラ法を使うと任意の２地点間の最短経路が求められますが、最短経路だけでなく最長経路など任意の２地点間における全ての経路を求めたいと考えていますが、なかなか良いアルゴリズムができません。詳しい方御教授お願いいたします。
- 締切済み
- 数学・算数
- 最短経路問題のアルゴリズム
最短経路問題のアルゴリズムにはどのようなものがありますか？ ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。
- ベストアンサー
- 数学・算数
- 最短距離を求める問題（ダイクストラ法）の原理
グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 巡回セールスマン問題を使って・・・
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。 文字数の関係で、プログラムをのせれないのでお答えになってくださったときにお礼の場でプログラムをお見せすることができます。
- 締切済み
- Visual Basic
- 巡回セールスマン問題の考え方を使って・・・。
以前、この場で巡回セールスマン問題の考え方を使って、ということで質問に答えていただきました。その節はありがとうございました。 建築の学生なのですが、卒論の対象地の一つの分析として次のようなことを行っております。 対象地に1４の交差点があって 「１４の交差点全てを一筆書きで、最短経路で通過したい。」 ということをやるようになってます。 これに関して数人の方の協力でプログラムを組んでもらいました。 現在のプログラムはスタートのみ固定して、１４それぞれ最短経路を探索し、ルートと最短距離を表示します。 今度はこれを、スタートとゴールともに固定して 「スタートが交差点１で、ゴールが交差点14のとき ルートは・・。最短距離は何ｍ。」 というふうに表示させたいのですが、プログラムに関して私はまったく素人でどのように変更すればよいかわかりません。 そこで、どのように改良すればよいか教えていただけないでしょうか。 よろしくお願いします。
- ベストアンサー
- 数学・算数
