JAVAで最短経路を求める

質問

１、ある点からある点への、最短経路を求める方法
教えてください!
最初Cと間違えてて、いろいろ考えたけど
何か違うみたいで。。
点から点への道には、所要時間が設定してあります。

２、１とにてるんですけど、
すべての点を最短経路で通る方法。
同じく道には所要時間が設定してあります。
このときは出発点、到着点は気にしないです。
とにかくすべての点を通ればいいみたいです。

かなりさっぱりで困ってます。
どうか方法教えてください、よろしくお願いします。

回答No.2

imogasi · ベストアンサー

http://gtr01.adin.hamamatsu-u.ac.jp:8080/Apl24.html
ダイクストラ法による最短経路計算手順書
ほか「ダイクストラ法」「ダイクストラ」でＷＥＢ照会して、適当なものを見つけ、勉強されてはどうですか。
まずこのアルゴリズムを理解する必要があります。判れば
コーディングは易しいのではないでしょうか。
ＣやＪａｖａのアルゴリズム入門（河西 朝雄氏や奥村氏の本）にも載っているでしょう。
Javaによるアルゴリズム事典
奥村 晴彦 (著)
http://www.amazon.co.jp/exec/obidos/ASIN/4774117293/inktomi-jp-asin-books-22/250-3830052-0873024

お礼

回答ありがとうございます。
ダイクストラ法で検索したら、
いい感じのページを見つけることができました。
助かりました！

回答No.1

neue_reich

否定的意見で申し訳ないのですが、これはＮＰ完全といわれる類の問題ですね。
１、はともかく（ＮＰ完全ではないと思いますが、かなり手数がかかります）
２、については「セールスマン巡回問題」と言われ、
アメリカの主要都市（２００くらい）を対象にした場合でも、
答えを求めるのに何万年もかかってしまう、という代物です。

点の数が少なければ、各点で一番時間が少ないもの、２番目に少ないものを使って各経路の所要時間を求め、
最短のものを選ぶ方法が良いかと思います。
工夫の余地はかなりありますし、さまざまな論文もありますので
調べてみるのが良いかとおもいます。

お礼

回答ありがとうございます。
１はなんとかできたのですが、
２は？？？です（＾＾；
もう少しいろいろ調べてみたいと思います。