幅優先探索、最短経路問題について

最短経路問題について。コストのある簡単な地図を使って最短経路を求めるプログラミングで一応最短経路を求めることができたのですが、うまくその表示させることができません。ヒントでも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<string> 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<vector<int> > dist(height, vector<int>(width, -1));
	dist[sx][sy] = 0; // スタートを 0 に

	// 探索中に各マスはどのマスから来たのかを表す配列 (最短経路長を知るだけなら、これは不要)
	vector<vector<int> > prev_x(height, vector<int>(width, -1));
	vector<vector<int> > prev_y(height, vector<int>(width, -1));

	// 「一度見た頂点」のうち「まだ訪れていない頂点」を表すキュー
	queue<pair<int, int> > que;
	que.push(make_pair(sx, sy)); // スタートを push


	////////////////////////////////////////
	/* 幅優先探索を実施 */
	////////////////////////////////////////

	/* キューが空になるまで */
	while (!que.empty()) {
		pair<int, int> 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は右下が０になってしまっているので、おそらくコストの計算がどこかまちがっているかもしれません。

ここまで試行錯誤してきましたがうまくいきません。

少しでも教えていただけると幸いです。

gentaro

2020/12/07 16:11

【至急】と付けるぐらい急いでるなら、ボランティアの回答を期待するのではなく、クラウドソーシング等でお金を払って教えて貰える人を探しましょう。あなたが急いでるのかどうかは回答者にとって何の関心もない話なので、それを求めるのはここでは嫌われる行為です。

KojiDoi

2020/12/07 18:20

[こんなタイトルで質問してはいけない - Qiita](https://qiita.com/doikoji/items/7cf9e659095816ab1131)

040LS

2020/12/07 19:22

初心者で何もわかりませんでした。すいません。

Zuishin

2020/12/07 22:57

できないということは、自分で組んだものではなく他人のコードを意味もわからず流用したものですよね？ならば必ず出典を書きましょう。そしてやりたいことだけ要求するのではなく、まずコードを読むところから始めましょう。読めないほどの初心者なら、初心者を脱して読めるようになるのが先です。小学生が大学の問題を解こうとして、何もわからず他人に解いてもらってもただの時間の無駄でしかありませんが、順を追って学習していくなら、いくら時間がかかってもそれは無駄ではありません。

fana

2020/12/08 05:26

> distに注目して、ゴールが右上のｘが７，ｙが０のところで、このときのコストが13です。 > つまりゴールまでコスト13でつくはずです。もうここから話がわからない． (1)コード内ではxが縦でyが横の方向に使われているように見えるから，ゴールの位置というは x=0,y=7 ではないのか？ (2)field の内容が書いてある箇所を眺めるに，コスト13でゴールにいけるように思えない．（SとGの市街地距離が14なのだから，曲がりくねった経路をたどるならば13で行けるはずがないと思う）

040LS

2020/12/08 06:24

ご指摘ありがとうございます。S,Gはコストに含まれないので13でいけると思います。最短経路を求める部分はできていて、うまくいっていると思うのですが、結果出力の部分がうまくいきません。

fana

2020/12/08 07:23

Sから右に4個行って，上に２個行って…… と，'1'のマスだけ辿っても17くらい必要に見えるのですが…？

040LS

2020/12/08 15:37

失礼しました。こっちでやっていました。 field[0] = "G111222#"; 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] = "1111111S";