• 締切済み

最短経路を計算するプログラム

下の図のようなものを用いて、スタート（S）からゴール（G）までいく最短経路を計算するプログラムをVisual Studio 2005のC++で作ったアルゴリズムが知りたいです。

画像を拡大する

みんなの回答

  • number44
  • ベストアンサー率27% (20/72)
回答No.1

ダイクストラ法でいいんですよね？ 有名な方法なので調べればサンプルは沢山出てくると思いますよ http://www.deqnotes.net/acmicpc/dijkstra/ ただ，本で調べるのが一番だと思います

alice_m
質問者

お礼

迅速な回答ありがとうございます。 明日、さっそく書店と図書館をはしごしたいと思います。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • 最短経路表示の追加プログラム

    下のリンク先のプログラムはダイクストラを用いた最短”距離”を求めるプログラム何ですが、このプログラムに最短距離の最短”経路”を表示する追加のプログラムを求めているんでけど、よろしければお答えしてもらえませんか？http://www.nda.ac.jp/~yamada/programs/programs.html

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

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

  • 経路探索

    よろしくお願いします。 現在経路探索問題のプログラムを書いています。 そこでわからない点があったので教えてください。 以下のような(n行,m列)の経路があります。 (0,0)－(0,1)－(0,2)－(0,3) (1,0)－(1,1)－(1,2)－(1,3) (2,0)－(2,1)－(2,2)－(2,3) (3,0)－(3,1)－(3,2)－(3,3) (4,0)－(4,1)－(4,2)－(4,3) スタートを(4,3)としてゴール(0,0)にたどり着く全ての経路を求めたいです。 条件としてある点から 左(例えば(4,3)⇒(4,2)) 上(例えば(4,3)⇒(3,3)) 斜め(例えば(4,3)⇒(3,2)) にしか進むことはできません。 このような仕様のアルゴリズムはどのように書けばよいのでしょうか？？ ご解答要路しくお願いします。

  • 最短経路について

    正方形を横に5個、縦に4個ならべた碁盤を考える(つまり線の上を通る) このとき左下にＡ地点、右上にＢ地点を置き、Ａ地点から2つ右上の(つまりＡ地点から右に2つ、上に2つ行くと到達する)地点にＰ地点を置くとする (1)Ｐ地点が右左折禁止(つまり通過するときは直進することしかできない)の場合、Ａ地点からＢ地点まで行く最短経路は全部で何通りあるか 答えには左から右へＰ地点を直進する場合と下から上へＰ地点を直進する場合に分けて、前者は3Ｃ1×4Ｃ2、後者は3Ｃ1×4Ｃ1通りでそれらとＰ地点が通行止めのときのＡ地点からＢ地点までの最短経路の全体を足しているのですが3Ｃ1×4Ｃ2と3Ｃ1×4Ｃ1がどういう意味か分かりません 教えてください

  • 最長経路探索

    グラフの最長経路(クリティカルパス)を求めたいのですが、 ・閉路無し有向グラフ ・重み付きグラフ（辺ではなくノードの方に重みがある） ・スタートとゴールのノードが各々1つ与えられている ・スタートからどの経路を辿ってもゴールには辿り着く 以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか？ 幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。 言語はVBAで、そもそも詳しくないのですが、 考え方など教えて頂けないでしょうか。 お願い致します。

  • 迷路プログラム

    迷路プログラムの応用問題なのですが、上手くいかずに困っています。 問題 2次配列を用いて、縦横X,Yマスの迷路を作ります。 マスの数はX,Y共に最大100までの値であれば、任意の数が振れます。 迷路の一番左下がスタートS、一番右上がゴールGになります。 マスへは上下左右にしか移動出来ません。 迷路の中には任意で入力したXマスがあり、Xが入っているマスには移動出来ません。 S,G,Xが入っていないマスには、1～9までの数字を任意に入力します。 それぞれの数字は、そのマスに移動するためにかかるコストを表しています。 スタートからゴールまで、コストがもっとも小さくすむルートのコストを出力するプログラムを作りたいです。 また、Xマスでゴールが不可能な場合は-1を返します。 単純にゴールを目指すのと違い、コストがあると遠回りをしなければならない可能性があるので、そのアルゴリズムが思いつきませんでした。 例 11*7マスの迷路の場合 マスの数：11 7 迷路の値の入力： 7 9 3 3 6 3 X X 7 9 G 1 1 3 2 6 6 8 4 8 4 5 7 2 9 1 3 4 8 4 9 8 9 9 7 4 2 5 X 8 6 9 9 4 4 7 3 8 X 8 X 5 7 X 7 1 7 1 8 5 6 5 9 5 6 2 S 5 5 2 9 4 2 2 9 5 1 出力： 最小コストは59 迷路からゴールに進むだけのプログラムは作れたのですが、応用問題としてコストが入ると急に難しくなりました。 コストが絡むとどういうアルゴリズムで動けばいいのか分かりません。アドバイスをお願いします。

  • 最短路問題について

    はじめまして。 「データ構造とアルゴリズム」を独学で勉強中の学生です。 当方、周りより指導していただける環境が無く どうにも行き詰まってしまったのでここに書き込みをさせていただきました。 お聞きしたい問題なのですが 「最短路問題について問題の定義と解法(アルゴリズム)を説明せよ。次に図１においてpから全ての頂点への最短路を求めよ。」 というものです。 * 図１はhttp://www.geocities.co.jp/Hollywood-Stage/3151/g/g.gifにupしてあります。 最短路問題を解く方法としてダイクストラのアルゴリズムやFloydのアルゴリズムがありますが、これらは書籍などを参考にして理解しているつもりです。 しかし実際、問題を解く手順といいますか、解答を書くことができないのでどなたかおわかりになる方がいらっしゃいましたらご指導をいただきたいと思い書き込みをさせていただきました。 学習不足で怠慢な学生の質問で大変申し訳ありませんが ご指導のほどよろしくお願いいたします。

  • 最短距離でいく経路の場合の数を教えてください。

    最短距離でいく経路の場合の数を教えてください。 図のような道路で、点Pから点Qまで最短距離でいく経路のうち、次の経路は何通りあるか。 問1.すべての経路 問2.Rを通る経路 答案1. 横道路が4本、縦道路が6本 最短距離でいくから階段状に行くのはいいけど、矩形上にジグザグにいくのはダメですよね。 和の法則＝「同時に起こらない場合｣＝排反事象 ある試行において、一方が起これば　他方は決して起こらないときの、それぞれの事象。 今回全くわかりません。 横道路4本のうち4本とも行くことが出来るので4C4 ? 縦道路6本のうち6本とも行くことが出来るので6C6 ? たとえば 横1縦6 横1縦5横4 縦1横4 縦1横3縦6 規則は必ず横1か縦1を通る。 最後は横4か縦6を通る。 わかりません。 答案2. 考え方から全くわかりません。

  • 最短経路問題を1つ算出するスクリプト

    お世話になります。 以下のようなファイルを利用して、最短経路を求めるスクリプトをご教示いただけないでしょうか。 Metricがもっともすくないものが良。 可能な限りC言語以外で実現したいと考えております。 ## 検索してみたのですが、どうもC言語のプログラムが多そうです。 (snip) Source Dest Metric 1 2 1 1 3 1 4 1 5 4 3 4 4 5 1 4 6 1 4 7 5 4 8 4 4 9 2 4 10 7 4 11 6 4 12 14 4 13 9 4 14 12 4 15 23 4 16 27 4 17 20 18 19 1 19 7 4 20 18 4 20 19 2 21 19 2 2 4 2 2 3 1 2 7 2 ・・・・・・ ・・・・・ ・・・・ ・・・ ・・ (snip)

  • C#で経路データのようなものを入力として扱うことはできるのか？

    C#で経路データのようなものを入力として扱うことはできるのか？ ただいまC#でプログラムを組んでいるのですが、 2次元の複数の経路図のようなものをあらかじめ何かのツールで作成しておき、 この経路図を入力として入力すると、似ている経路同士でグルーピングを行う というプログラムを作りたいと考えております。 プログラムのコアとなる似ているかどうかを判断する部分に関しては すでにコーディング済みです。ちなみにこの部分の処理は、クラスター分析という概念を用いており、 あらかじめ紙などに書いた経路から"自分で座標を求め"、コーディングしたツールに入力しておりました。 つまりこれまでは 自分で経路図を紙などに書いて想定→何個かの点の座標を把握→作成ツールに座標値入力 という手間をとっていたのですが、 今回はその進化版として、経路図をそのまま入力として扱えるようにしたい、つまり上記の手間を省いてグループわけをしたいと考えております。 背景はこのような感じです。 主に僕が知りたいな部分としては 入力した経路図から、どのようにしてその経路の複数個の点の座標を得るのか？ ということです。ちなみにこれまでは紙に書いた経路から自分で求めていました。 その経路の複数個の点の座標が求められれば、あとはすでにコーディング済みの計算処理部にかければ処理を行うことができます。 まとめると・・ ・他ツールで作成した（？）経路図のような2次元の図を、C#で入力として入力することはできるのか？ ・できたとしたらどのツールで経路図を作成すればいいのか？ （経路は複数個を想定しているので経路の区別も必要） ・どのようにしてC#に入力をすればいいのか？（ソース的な面） そして一番大事な 「入力された経路図からどのようにして複数個の点を得るのか？」 です。 難解な点もありますがどうぞよろしくお願いいたします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する