(C++) BFS求解最短路长度及最短路路径

一、问题描述：（迷宫问题）

在一张由0， 1构成的图中，1表示障碍，0表示通路 给定起点S和终点T 求从S到T的最短路长度并输出路径

二、求解思路：（BFS）

首先BFS是由队列实现和队列先进先出的特性， 对于求最短路长度，我们可以从终点T开始倒着搜索， 用一个数组dist[][]表示每个点到终点T的最短路径， 如果一个点能由上一个点一步走到，则将该点入队，直到队列为空即遍历完所有的点。 对于求路径，可以在dist数组的基础上，从起点开始搜索， 如果有一点能由当前点一步走到，则该点一定在最短路径上。

三、代码实现：

#include<iostream> #include<cstring> #include<queue> using namespace std; const int maxn = 1010; char mp[maxn][maxn];//存放地图 int dist[maxn][maxn];//距离矩阵 记录各个点到终点的最短路长度 int n; int sx, sy, tx, ty;//记录起止点的横纵坐标 int dx[4] = {1, 0, 0, -1}, dy[4] = {0, -1, 1, 0};//用来方便往四个方向走 char dir[4] = {'D', 'L', 'R', 'U'}; void bfs() { for(int i = 0; i < n; i ++) //将dist数组初始化为无穷大 for(int j = 0; j < n; j ++) dist[i][j] = 1e9; dist[tx][ty] = 0;//终点到终点距离为零 queue<pair<int, int> > q;//bfs用队列实现，这里用pair记录点的横纵坐标，当然用结构体实现也是可以的 pair<int, int> t;//临时用的 t.first = tx; t.second = ty; //用t记录终点 q.push(t);//终点入队 while(q.size()){ t = q.front();//每次取出队头元素 q.pop();//队头元素出队 for(int i = 0; i < 4; i ++){//遍历队头元素可以往哪走 int nx = t.first + dx[i]; int ny = t.second + dy[i];//这两句话实现了往一个方向走，想不明白可以在纸上画一下 if(nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == 1e9 && mp[nx][ny] != '1'){ //条件的作用分别是：判断是否越界；判断是否走过（如果走过了，dist的值一定被改变了）；判断是否可走（障碍物则此路不通） dist[nx][ny] = dist[t.first][t.second] + 1;//满足条件则为上一个点多走一步，离终点的距离也就多1 q.push(make_pair(nx, ny));//将该点入队，方便下次从该点出发遍历 } } } } int main() { cin >> n; for(int i = 0; i < n; i ++){ //输入图并记录起止点的坐标 for(int j = 0; j < n; j ++){ cin >> mp[i][j]; if(mp[i][j] == 'S'){ sx = i; sy = j; } if(mp[i][j] == 'T'){ tx = i; ty = j; } } } bfs();//开始搜索 cout << dist[sx][sy] << endl;//起点到终点的最短路长度 int x = sx, y = sy; while(x != tx || y != ty){ for(int i = 0; i < 4; i ++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < n && mp[nx][ny] != '1'){ //条件含义和上面一样，这里不再赘述 if(dist[x][y] == dist[nx][ny] + 1){ //如果下一个点能由当前节点一步走到，则下一点一定在最短路径上 cout << dir[i] << endl;//输出方向 x = nx; y = ny; //更新x ,y break; } } } } return 0; }

四、运行结果：

随便测了一个数据，大家可以去各个OJ找相关题目，按照思想去试一下

五、变形

可以修改的地方有很多，这里主要说一种修改的输出方式 只需要修改main函数中遍历输出的部分即可

代码如下

int x = sx, y = sy cout << "(" << x << ", " << y << ")" << endl; while(x != tx || y != ty){ for(int i = 0; i < 4; i ++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < n && mp[nx][ny] != '1'){ if(dist[x][y] == dist[nx][ny] + 1){ cout << "(" << nx << ", " << ny << ")" << endl; x = nx; y = ny; //更新x ,y break; } } } }

结果如下