0979デフォルトの名無しさん
2020/01/15(水) 13:45:14.74ID:oHYk5H5Qありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・?
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。