最短経路問題について。コストのある簡単な地図を使って最短経路を求めるプログラミングで一応最短経路を求めることができたのですが、うまくその表示させることができません。ヒントでもC++のコードでも少しでもいいので教えていただきたいです。初心者で細かいところがよくできていなく、指摘したい場所やみづらいコードとなっているかと思いますが、お手柔らかにお願いします。 ``` #include "ofApp.h" //-------------------------------------------------------------- void ofApp::setup() { /* 4 方向への隣接頂点への移動を表すベクトル */ const int dx[4] = { 1, 0, -1, 0 }; const int dy[4] = { 0, 1, 0, -1 }; //////////////////////////////////////// /* 入力受け取り */ //////////////////////////////////////// /* 縦と横の長さ */ int height, width; //cin >> height >> width; height = 8; width = 8; /* 盤面 */ vector field(height); //for (int h = 0; h < height; ++h) cin >> field[h]; field[0] = "1#1222#G"; field[1] = "1#1#1111"; field[2] = "111#1##1"; field[3] = "#1##111#"; field[4] = "111###1#"; field[5] = "9#111111"; field[6] = "922#1##1"; field[7] = "S1111111"; /* スタート地点とゴール地点 */ int sx, sy, gx, gy; for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { if (field[h][w] == 'S') { sx = h; sy = w; } if (field[h][w] == 'G') { gx = h; gy = w; } } } //////////////////////////////////////// /* 幅優先探索の初期設定 */ //////////////////////////////////////// // 各セルの最短距離 (訪れていないところは -1 としておく) vector > dist(height, vector(width, -1)); dist[sx][sy] = 0; // スタートを 0 に // 探索中に各マスはどのマスから来たのかを表す配列 (最短経路長を知るだけなら、これは不要) vector > prev_x(height, vector(width, -1)); vector > prev_y(height, vector(width, -1)); // 「一度見た頂点」のうち「まだ訪れていない頂点」を表すキュー queue > que; que.push(make_pair(sx, sy)); // スタートを push //////////////////////////////////////// /* 幅優先探索を実施 */ //////////////////////////////////////// /* キューが空になるまで */ while (!que.empty()) { pair current_pos = que.front(); // キューの先頭を見る (C++ ではこれをしても pop しない) int x = current_pos.first; int y = current_pos.second; que.pop(); // キューから pop を忘れずに // 隣接頂点を探索 for (int direction = 0; direction < 4; ++direction) { int next_x = x + dx[direction]; int next_y = y + dy[direction]; if (next_x < 0 || next_x >= height || next_y < 0 || next_y >= width) continue; // 場外アウトならダメ if (field[next_x][next_y] == '#') continue; // 壁はダメ // まだ見ていない頂点なら push if (dist[next_x][next_y] == -1) { que.push(make_pair(next_x, next_y)); string cost_str{ field[next_x][next_y] }; // field[next_x][next_y]がchar型なのでstring型に変換 if (field[next_x][next_y] != 'G') { // Goalでなければ // 次のマスに進む場合のコストの算出部分 // 現状だと，（x,y）から（next_x, next_y）に進んだ場合のコストを算出している dist[next_x][next_y] = dist[x][y] + stod(cost_str); // (next_x, next_y) の距離も更新 // 本来すべきこと // （x,y）からのコストではなく，上下左右のどのマスでもいいので，最小コストから // （next_x, next_y）に進む際のdistを記録すべき } prev_x[next_x][next_y] = x; // どの頂点から情報が伝播して来たか、縦方向の座標をメモ prev_y[next_x][next_y] = y; // どの頂点から情報が伝播して来たか、横方向の座標をメモ } } } // fieldの出力 cout << "field" << endl; for (int i = 0; i < field.size(); i++) { cout << field[i] << endl; } cout << endl; // distの出力 cout << "dist" << endl; for (int i = 0; i < dist.size(); i++) { for (int j = 0; j < dist[i].size(); j++) { cout << "\t" << dist[i][j]; } cout << endl; } //////////////////////////////////////// /* 結果出力 */ //////////////////////////////////////// // 正しいdistが算出できたら，distが最小となる経路を // ゴールの方からスタートに向かって逆に探索する // backward int x = gx, y = gy; while (x != -1 && y != -1 && dist[x][y] > 0) { field[x][y] = 'o'; // 通過したことを示す // 前の頂点へ行く int px = prev_x[x][y]; int py = prev_y[x][y]; x = px, y = py; } for (int h = 0; h < height; ++h) { for (int w = 0; w < width; ++w) { cout << std::setw(3) << field[h][w]; } cout << endl; } } コード ``` distに注目して、ゴールが右上のｘが７，ｙが０のところで、このときのコストが13です。つまりゴールまでコスト13でつくはずです。そこから逆にたどって経路は，今回の場合は「右，上，左」のいずれかに進むような進み方だったと思うので、逆にたどる場合は、ゴールの左と下のマスを見てみるはずです。どちらから来たかを判定するための比較文を書き、-1は壁なので無視すると，下のマス（コスト12）から来たことがわかるかと思います。そのマスはｘは７でｙは１で、次に，ｘ＝７，ｙ＝１のマスから見て，左，下のマスを見ると，左のマスの方がコストが小さいです。つまりｘ＝６，ｙ＝１のマスから来たということがわかると思います。このようにスタートまでたど履帯です。 distは右下が０になってしまっているので、おそらくコストの計算がどこかまちがっているかもしれません。ここまで試行錯誤してきましたがうまくいきません。少しでも教えていただけると幸いです。

	@@ -1 +1 @@
1	- ~~【至急】~~幅優先探索、最短経路問題について
1	+ 幅優先探索、最短経路問題について

質問編集履歴