Q&A
> 以下の2経路です。
求めなければならないのは「最短距離（＋実際に満たす1経路）」だけでしょうか、それとも「最短距離となるすべての経路」でしょうか？
最短経路に少しにた問題のアルゴリズムについて
スタートC、ゴールCとしたとき最短経路を求めたいです。
- C->B->Cのような同じ道を戻ることはNG
- C->Cのようにスタート地点から離れないのもNG
どのようなアルゴリズムで解くことができますか？
（ダイクストラ法をそのまま適用するとC->Cとなってしまいます。全探索しかないでしょうか？）
結果
最短経路は39mで以下の2経路です。
C->B->X->C
C->D->X->C
ご質問ありがとうございます。最短距離となるすべての経路になります。
> 以下の2経路
ということは，
C->X->B->C みたいな「他と被ってる」のが結果に入らないようにする必要があるのかな．
（ここに書いた話を「回答」側に移したので削除）
パッと見てダミー的な終点を新たに追加すればどうでしょうか。
Cと直接つながっているB,X,Dに対して、等距離にあるZをおいて結び
経路としてはC→Zの最短をとるものを探す。
といった感じで行けそうな気がします。
いや、ダメっぽい。
みなさまありがとうございます。
繋がってないものとするや、ダミー終点を置くなど、解くための一工夫参考になります。
fanaさんの方法で進めてみようと思います。
ありがとうございました！
> 進めてみよう
という段階で早急にBAを付けなくても，
実際にやってみた結果：｛OKだった，それじゃダメだった，そのままではちょっとなぁ…ということころはこうして対処した，etc｝ が見えてから付ければいいんじゃないかな，とか．
回答1件
0
ベストアンサー
何らかの最短経路探索アルゴリズムを用いることに関して「スタートとゴールが同じ地点であることが弊害となっている」という話なのであれば，そのアルゴリズムを用いて
- B から C に行くための最短経路を B-C が繋がっていないものとして求める（で，その結果経路の先頭に C->B を加える）
- X から C に行くための最短経路を X-C が繋がっていないものとして同上
- D から C に行くための最短経路を D-C が繋がっていないものとして同上
ということをして，これら３つの結果を比較すれば良いのではないでしょうか．
投稿2023/01/31 04:18
総合スコア11658
＃
「……っていう話がまずは普通に考えられる気がするのですが，それだとどうなんですか？ 何かがダメとかありますか？」
という問いかけ的ニュアンスで，先に[質問へのコメント]欄の方にこの内容を書いたのだけど，
個々の話をする場所が分離していた方が応答をしやすい（し，それを見やすい）と思ったので「回答」に移動しました．
あなたの回答
tips
プレビュー
