- ベストアンサー
最短経路問題のアルゴリズム
最短経路問題のアルゴリズムにはどのようなものがありますか？ ダイクストラくらいしか知りません。教えてください。 カテゴリー違いだったら書き直します。
- special1998
- お礼率0% (0/41)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ダイクストラ法が最も有名かつ実用的にも良いですが 負の長さの枝があると困ってしまうんですよね。 これ以外の方法で知っておくと良いのは、 Bellman-Ford法くらいでしょうか。 この方法は、ダイクストラ法に劣る部分もありますが 負の長さの枝があってもちゃんと動作する、 負閉路がある場合、それを確認できるという利点が あるので覚えておくのも良いと思います。 アルゴリズムの詳細は、上の名前から検索すると 見ることができると思います。 ＃別の回答にある、幅優先探索・深さ優先探索などは 非常に重要なアルゴリズムですが、今回の目的に 利用することができるかどうかは調べてみて下さい
その他の回答 (1)
- sunasearch
- ベストアンサー率35% (632/1788)
幅優先探索 深さ優先探索 A*アルゴリズム
関連するQ&A
- ベルマンフォードのアルゴリズム
このカテゴリーであってる・・・かな・・。 とりあえず、ネットワークのアルゴリズムなので。 最短経路を求めるアルゴリズムは、 ダイクストラしか知らなかったのですが、 ベルマンフォードというアルゴリズムがあると知りました。 どのようなアルゴリズムなのでしょうか？ ダイクストラと比較してどうなのでしょうか？
- ベストアンサー
- その他（インターネット接続・通信）
- 最短経路のアルゴリズム
このジャンルでお願いします。 左下の座標を(1,1)として ○(4,4)が△(7,2)に辿りつく最短経路のアルゴリズムが知りたいです。 ■は通れない場所です。 □□□□□□□ □□■■□□□ □□□□■□□ □■□○■□□ □■□■■□□ □□■□□△□ □□□□□□□ ↑ (1,1)
- ベストアンサー
- C・C++・C#
- 任意の2地点間の全経路探索について
ネットワーク上においてダイクストラ法を使うと任意の２地点間の最短経路が求められますが、最短経路だけでなく最長経路など任意の２地点間における全ての経路を求めたいと考えていますが、なかなか良いアルゴリズムができません。詳しい方御教授お願いいたします。
- 締切済み
- 数学・算数
- 最短路問題について
はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図１においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図１はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。
- ベストアンサー
- その他（学問・教育）
- 最短経路表示の追加プログラム
下のリンク先のプログラムはダイクストラを用いた最短”距離”を求めるプログラム何ですが、このプログラムに最短距離の最短”経路”を表示する追加のプログラムを求めているんでけど、よろしければお答えしてもらえませんか？http://www.nda.ac.jp/~yamada/programs/programs.html
- 締切済み
- C・C++・C#
- 最短距離を求める問題（ダイクストラ法）の原理
グラフ（経路）の情報があり、それを用いて最短距離を探索するアルゴリズムにダイクストラ法というものがあります。 このアルゴリズムでは常に正しい解を導けるということなのでしょうか。調べてみると負の距離があったらダメというのがありましたが、これは除外しての話ですが。 また、このアルゴリズムがなぜ正しいだろうと思えるのかについて理解できればなんとなくわかるような気がします。そこで、wikipediaを読んでみたのですが、さっぱり分かりませんでした。ちょっと引用します。 ”最短経路問題は、ビー玉と紐を用いて解くことが出来る。 まずビー玉を頂点、紐を辺にするグラフを工作する。 グラフを板の上に置き、スタートの頂点にあたるビー玉だけをつまむ。 グラフが置かれている板を取り除くと、グラフは自由落下を始めるが、 スタートにあたるビー玉を持っているので、スタート地点から近いビー玉から順に落下が止まる。 ゴールにあたるビー玉が止まったとき、ゴールにあたるビー玉はスタートにあたるビー玉まで紐で一直線で結ばれている。 この直線が最短経路である。” ビー玉が経路の構成点で紐が経路なのかなということはわかりますが、それを板の上にのせて板がを取り除く、あたりから何が何だかさっぱりわかりません。板は水平に置かれているなら板が消えたら全部落下するだけのように思えますし。でもこれが理解できるとアルゴリズムの思想が理解でき、その妥当性とか限界について予想がつくのだろうと思います。 他に何かイメージがつかみやすい説明があるでしょうか。 また、ダイクストラ法は情報処理としては初等的なものなのでしょうか。それとも結構アドバンスドなものなのでしょうか。 サンプルプログラムを調べてみたらC・C++が多いようなのでこちらにお尋ねしてみました。 よろしくお願いします。
- 締切済み
- C・C++・C#
- 最短経路を計算するプログラム
下の図のようなものを用いて、スタート（S）からゴール（G）までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。
- 締切済み
- C・C++・C#
- この問題は最短経路の考え方でいいのでしょうか？
この問題は最短経路の考え方でいいのでしょうか？ さいころを振って、xy平面上に置かれた駒を次の規則にしたがって動かす。 出た目が１または２ならばx軸方向に１だけ移動させ、 出た目が３または４ならばy軸方向に１だけ移動させ、 出た目が５または６ならば駒はその点にとどめる。 （１）OからAへの最短経路は全部で何通りあるか？ （２）さいころを7回振ったとき駒が初めてAに到達する確率を求めよ。 （３）さいころを9回振ったとき駒が初めてAに到達する確率を求めよ。
- 締切済み
- 数学・算数
