在路径规划方面，迷宫搜索是验证图遍历算法的标准场景，这里将简单介绍一下四种核心算法：深度优先搜索(DFS)、广度优先搜索(BFS)、Dijkstra 算法以及 A* 算法的原理以及C++的实现。
在无权图即迷宫各路径代价相等中，DFS和BFS是两种最基本的策略。
一、迷宫的定义
1.基础常量与数据结构
迷宫的每个节点有 4 个移动方向，先定义核心常量：
#include <iostream>
#include <stack>
// 迷宫每个节点的4个方向
const int RIGHT = 0;
const int DOWN = 1;
const int LEFT = 2;
const int UP = 3;
// 迷宫每个节点方向的数量
const int WAY_NUM = 4;
// 节点的行走状态
const int YES = 4;
const int NO = 5;
// 迷宫节点信息
struct Node
{
int x;
int y;
int val;
int state[WAY_NUM];
};2. 迷宫基础模型
迷宫类定义如下：
#include <iostream>
#include <stack>
class Maze
{
public:
Maze(int _col, int _row) : col(_col), row(_row)
{
pMaze = new Node *[row];
for (size_t i = 0; i < row; i++)
{
pMaze[i] = new Node[col];
}
}
// 析构函数：释放内存
~Maze() {
for (size_t i = 0; i < row; i++) {
delete[] pMaze[i];
}
delete[] pMaze;
}
void initNode(int x, int y, int val)
{
pMaze[x][y].x = x;
pMaze[x][y].y = y;
pMaze[x][y].val = val;
for (int i = 0; i < WAY_NUM; ++i)
{
pMaze[x][y].state[i] = NO;
}
}
// 初始化迷宫0节点四个方向的行走状态信息
void setNodeState()
{
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; ++j)
{
if (pMaze[i][j].val == 1)
{
continue;
}
// 当前节点的右边，值如果是0，表示可以走
// 右：判断列不越界且右侧节点可走
if (j < col - 1 && pMaze[i][j + 1].val == 0)
{
pMaze[i][j].state[RIGHT] = YES;
}
// 下：判断行不越界且下侧节点可走
if (i < row - 1 && pMaze[i + 1][j].val == 0)
{
pMaze[i][j].state[DOWN] = YES;
}
// 左：判断列不越界且左侧节点可走
if (j > 0 && pMaze[i][j - 1].val == 0)
{
pMaze[i][j].state[LEFT] = YES;
}
// 上：判断行不越界且上侧节点可走
if (i > 0 && pMaze[i - 1][j].val == 0)
{
pMaze[i][j].state[UP] = YES;
}
}
}
}
private:
int col; // 列数
int row; // 行数
Node **pMaze; // 迷宫二维数组
std::stack<Node> stack; // 保存DFS路径的栈
};以 6×6 迷宫为例，迷宫定义如下：
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 0 0 0 00表示通路，1表示墙壁，迷宫入口为 (0,0)，迷宫出口为：(5,5)。
二、深度优先搜索
深度优先搜索（Depth First Search，DFS）优先访问节点的后继节点。在迷宫中，它沿着一条路径持续推进，直到遇到障碍或者边界，随后通过回溯，返回上一个分叉点。
它的实现方式是使用递归或栈。
#include <iostream>
#include <stack>
class Maze
{
public:
Maze(int _col, int _row) : col(_col), row(_row)
{
//同上，略
}
void initNode(int x, int y, int val)
{
//同上，略
}
// 初始化迷宫0节点四个方向的行走状态信息
void setNodeState()
{
//同上，略
}
void searchMazePath()
{
// 没有入口，直接return
if (pMaze[0][0].val == 1)
{
return;
}
stack.push(pMaze[0][0]);
while (!stack.empty())
{
Node top = stack.top();
int x = top.x;
int y = top.y;
// 已经找到了右下角的迷宫出口
if (x == row - 1 && y == col - 1)
{
return;
}
// 先往右找
if (pMaze[x][y].state[RIGHT] == YES)
{
pMaze[x][y].state[RIGHT] = NO;
pMaze[x][y + 1].state[LEFT] = NO;
stack.push(pMaze[x][y + 1]); // 如果右边能走，就入栈
continue; // 回到开头，重新去上面入栈的右边，继续判断
}
// 如果右边走不了，就往下
if (pMaze[x][y].state[DOWN] == YES)
{
pMaze[x][y].state[DOWN] = NO;
pMaze[x + 1][y].state[UP] = NO;
stack.push(pMaze[x + 1][y]);
continue;
}
// 往左查找
if (pMaze[x][y].state[LEFT] == YES)
{
pMaze[x][y].state[LEFT] = NO;
pMaze[x][y - 1].state[RIGHT] = NO;
stack.push(pMaze[x][y - 1]);
continue;
}
// 往上查找
if (pMaze[x][y].state[UP] == YES)
{
pMaze[x][y].state[UP] = NO;
pMaze[x - 1][y].state[DOWN] = NO;
stack.push(pMaze[x - 1][y]);
continue;
}
// 如果4个方向都不能走，说明栈顶元素节点没有方向可走，出栈
stack.pop();
}
}
void showMazePath()
{
if (stack.empty())
{
std::cout << "不存在一条迷宫路径" << std::endl;
}
else
{
std::cout << "-------迷宫路径-------" << std::endl;
while (!stack.empty())
{
Node top = stack.top();
pMaze[top.x][top.y].val = '*';
stack.pop();
}
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < col; j++)
{
if (pMaze[i][j].val == '*')
{
std::cout << "* ";
}
else
{
std::cout << pMaze[i][j].val << " ";
}
}
std::cout << std::endl;
}
}
}
private:
// 迷宫节点信息
struct Node
{
int x;
int y;
int val;
int state[WAY_NUM];
};
int col;
int row;
Node **pMaze; // 动态生成迷宫
std::stack<Node> stack; // 辅助生成深度优先查找到的迷宫的路径
};
上述代码的核心逻辑：
- 栈的作用：栈用于保存当前行走的路径，栈顶始终是当前所在的节点。
- 方向优先级：代码中按 "右→下→左→上" 的顺序尝试，DFS 会优先沿着一个方向钻到底。
- 回溯机制：当当前节点四个方向都走不通时，执行pop()出栈，回到上一个节点继续尝试其他方向。
- 防回头标记：将走过的路径双向标记为不可走（如向右走后，当前节点的 RIGHT 和右侧节点的 LEFT 都设为 false），避免重复走同一路径。
调用方法如下：
int main()
{
cout << "请输入迷宫的行列数，例如：10 10：";
int row, col, data;
cin >> row >> col;
Maze maze(row, col); //
cout << "请输入迷宫的路径信息(0表示可以走，1表示不能走)" << endl;
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
cin >> data;
maze.initNode(i, j, data);
}
}
maze.setNodeState();
maze.searchMazePath();
maze.showMazePath();
cout << endl;
return 1;
}运行：
请输入迷宫的行列数,例如：10 10
5 5
请输入迷宫的路径信息：0表示可以走，1表示不能走
0 0 0 1 1
1 0 0 0 1
1 1 0 1 1
1 1 0 0 1
1 1 1 0 0
-------迷宫路径-------
* * * 1 1
1 0 * 0 1
1 1 * 1 1
1 1 * * 1
1 1 1 * *再次运行一个不通的迷宫：
请输入迷宫的行列数,例如：10 10
5 5
请输入迷宫的路径信息：0表示可以走，1表示不能走
0 0 0 1 1
1 0 1 0 1
1 1 0 1 1
1 1 0 0 1
1 1 1 0 0
不存在一条迷宫路径DFS会一直沿着预定的方向探测，比如上面探测方向的顺序是 右-下-左-上，如果其中右边一直能走，它会一直往右边，如果下边能走，就一直往下边。
比如：
请输入迷宫的行列数,例如：10 10
6 6
请输入迷宫的路径信息：0表示可以走，1表示不能走
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 0 0 0 0
-------迷宫路径-------
* * 1 1 1 1
1 * * * * 1
1 0 1 1 * 1
1 * * * * 1
1 * 1 1 1 1
1 * * * * * 显然，这不是最优路线。
三、广度优先搜索
广度优先搜索(Breadth First Search，BFS)则不同，它会"层层推进"，先探索当前位置的所有相邻节点，再探索下一层节点，即BFS 按距离起点的步数分层扩展，它首先访问所有距离为 1 的节点，随后是距离为 2 的节点。
广度优先使用层层扩展的方式，依赖一个队列结构，在无权图中，BFS 首次到达终点的路径即为最短路径。其空间复杂度较高 O(V)，需存储所有已访问节点。
实现代码如下:
#include <iostream>
#include <mutex>
#include <string>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
class Maze
{
public:
Maze(int c, int r) : col(c), row(r)
{
pMaze = new Node *[row];
for (size_t i = 0; i < row; ++i)
{
pMaze[i] = new Node[col];
}
path.resize(row * col);
}
// 析构函数：释放内存
~Maze() {
// 同上
}
void initNode(int x, int y, int val)
{
//同上
}
// 观察当前节点的上下走有四个方向的元素是否可以走，如果可以，修改状态。
void setNodeState()
{
//同上
}
void searchMazePath()
{
if (pMaze[0][0].val == 1)
{
return;
}
queue.push(pMaze[0][0]);
while (!queue.empty())
{
Node top = queue.front();
int x = top.x;
int y = top.y;
// 已经找到右下角，得到迷宫路径
if (x == row - 1 && y == col - 1)
{
return;
}
// 如果往右可以走
if (pMaze[x][y].state[RIGHT])
{
pMaze[x][y].state[RIGHT] = false;
pMaze[x][y + 1].state[LEFT] = false; // 只走一遍
path[x * row + y + 1] = pMaze[x][y]; // 记录前驱节点（用于回溯路径）
queue.push(pMaze[x][y + 1]);
if (check(pMaze[x][y + 1]))
{
return;
}
}
// 如果往下可以走
if (pMaze[x][y].state[DOWN])
{
pMaze[x][y].state[DOWN] = false;
pMaze[x + 1][y].state[UP] = false; // 只走一遍
path[(x + 1) * row + y] = pMaze[x][y];
queue.push(pMaze[x + 1][y]);
if (check(pMaze[x + 1][y]))
{
return;
}
}
// 如果往左可以走
if (pMaze[x][y].state[LEFT])
{
pMaze[x][y].state[LEFT] = false;
pMaze[x][y - 1].state[RIGHT] = false; // 只走一遍
path[x * row + y - 1] = pMaze[x][y];
queue.push(pMaze[x][y - 1]);
if (check(pMaze[x][y - 1]))
{
return;
}
}
// 如果往上可以走
if (pMaze[x][y].state[UP])
{
pMaze[x][y].state[UP] = false;
pMaze[x - 1][y].state[DOWN] = false; // 只走一遍
path[(x - 1) * row + y] = pMaze[x][y];
queue.push(pMaze[x - 1][y]);
if (check(pMaze[x - 1][y]))
{
return;
}
}
queue.pop();
}
}
void showMazePath()
{
if (queue.empty())
{
cout << "不存在一条迷宫路径" << endl;
}
else
{
int x = row - 1;
int y = col - 1;
for (;;)
{
pMaze[x][y].val = '*';
if (x == 0 && y == 0)
{
break;
}
Node node = path[x * row + y];
x = node.x;
y = node.y;
}
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
if (pMaze[i][j].val == '*')
{
cout << "* ";
}
else
{
cout << pMaze[i][j].val << " ";
}
}
cout << endl;
}
}
}
private:
struct Node
{
int x;
int y;
int val;
bool state[WAY_NUM]; // 节点的前后左右4个方向是否可以走
};
bool check(Node &node)
{
return node.x == row - 1 && node.y == col - 1;
}
int row;
int col;
Node **pMaze;
queue<Node> queue; // bfs依赖的队列结构
vector<Node> path; // 记录bfs时，节点的行走信息
};上述代码的核心逻辑为:
- 队列的作用：队列用于保存待探索的节点，队首是当前处理的节点，处理完后出队，再将其所有可走的相邻节点入队。
- 前驱节点记录：path数组保存每个节点的上一个节点（前驱），用于找到出口后回溯完整路径。
- 层级扩展：BFS 会先处理完当前层的所有节点（同一距离的节点），再处理下一层，因此能保证找到最短路径。
- 终止条件：只要发现某个节点是出口，立即返回，因为 BFS 的第一个出口路径就是最短路径。
调用方法如下：
int main()
{
cout << "请输入迷宫的行列数，例如：10 10：";
int row, col, data;
cin >> row >> col;
Maze maze(row, col); //
cout << "请输入迷宫的路径信息(0表示可以走，1表示不能走)" << endl;
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
cin >> data;
maze.initNode(i, j, data);
}
}
cout << "======================" << endl;
maze.setNodeState();
maze.searchMazePath();
maze.showMazePath();
cout << endl;
return 1;
}运行:
请输入迷宫的行列数，例如：10 10：6 6
请输入迷宫的路径信息(0表示可以走，1表示不能走)
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 0 0 0 0
======================
* * 1 1 1 1
1 * 0 0 0 1
1 * 1 1 0 1
1 * 0 0 0 1
1 * 1 1 1 1
1 * * * * * 请输入迷宫的行列数，例如：10 10：6 6
请输入迷宫的路径信息(0表示可以走，1表示不能走)
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 0
======================
* * 1 1 1 1
1 * 0 0 0 1
1 * 1 1 0 1
1 * * * * 1
1 1 1 1 * 1
1 0 0 0 * * 四、Dijkstra 算法
上述不管是DFS还是BFS，都是无权图即路径中每一步的代价都是相等的。DFS可以用来判断连通性，BFS可以用来解决每一步代价相同迷宫即无权图的最短路径。而Dijkstra算法可以认为是BFS的升级版，它可以解决 每一步代价 / 权重不一样 的即带权图最短路径问题（比如迷宫里有的路难走，代价是 2、3、5...）。
在实现上，由于每一步的权重不一样，所以队列结构方面不能再使用BFS中的普通的先进先出队列，而要使用优先级队列中的小根堆。可以认为BFS算法是Dijkstra算法再所有边权重=1时的特列，Dijkstra是带权图的“高级BFS”。
为了表示权重，需要在原有的Node节点上增加权重字段，并且需要提供一个函数对象及仿函数（Function Object）用来方便优先队列即小根堆来使用，以方便代价小的对象先出。
struct Node
{
int x;
int y;
int val; // 0=路 1=墙 * =路径
int cost; // 代价权重
};
struct Compare
{
bool operator()(const Node &a, const Node &b)
{
return a.cost > b.cost; // 小根堆
}
};算法的代码实现如下：
#include <iostream>
#include <mutex>
#include <string>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
const int RIGHT = 0;
const int DOWN = 1;
const int LEFT = 2;
const int UP = 3;
const int WAY_NUM = 4;
/*
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 0 0 0 0
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 0
0 1 1 1 1 1
1 1 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 0
*/
class Maze
{
public:
Maze(int c, int r) : col(c), row(r)
{
pMaze = new Node *[row];
for (size_t i = 0; i < row; ++i)
{
pMaze[i] = new Node[col];
}
path.resize(row * col);
dist.resize(row, vector<int>(col, INT_MAX));
}
// 析构函数：释放内存
~Maze()
{
for (size_t i = 0; i < row; i++)
{
delete[] pMaze[i];
}
delete[] pMaze;
}
void initNode(int x, int y, int val, int cost = 1)
{
pMaze[x][y].x = x;
pMaze[x][y].y = y;
pMaze[x][y].val = val;
pMaze[x][y].cost = cost;
}
void searchMazePath()
{
// 优先队列（小根堆）
priority_queue<Node, vector<Node>, Compare> q;
if (pMaze[0][0].val == 1)
{
return;
}
pMaze[0][0].cost = 0;
dist[0][0] = 0;
q.push(pMaze[0][0]);
// 四个方向偏移量,右、下、左、上
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
while (!q.empty())
{
Node top = q.top();
q.pop();
int x = top.x;
int y = top.y;
// 已经找到右下角，得到迷宫路径
if (x == row - 1 && y == col - 1)
{
return;
}
// 旧代价，跳过
if (dist[x][y] < top.cost)
{
continue;
}
for (int d = 0; d < WAY_NUM; d++)
{
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= row || ny < 0 || ny >= col)
{
continue; // 越界
}
if (pMaze[nx][ny].val == 1)
{
continue; // 墙
}
// 新代价=当前代价+下一个节点的代价
int newCost = dist[x][y] + pMaze[nx][ny].cost;
if (newCost < dist[nx][ny])
{
dist[nx][ny] = newCost;
path[nx * row + ny] = top; // 记录节点的行走信息
q.push(pMaze[nx][ny]);
}
}
}
}
void showMazePath()
{
int x = row - 1;
int y = col - 1;
// 如果出口的前驱节点不存在 → 没路径
if (dist[x][y] == INT_MAX)
{
cout << "Dijkstra：找不到迷宫路径！" << endl;
return;
}
for (;;)
{
pMaze[x][y].val = '*';
if (x == 0 && y == 0)
{
break;
}
Node node = path[x * row + y];
x = node.x;
y = node.y;
}
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
if (pMaze[i][j].val == '*')
{
cout << "* ";
}
else
{
cout << pMaze[i][j].val << " ";
}
}
cout << endl;
}
}
private:
struct Node
{
int x;
int y;
int val; // 0=路 1=墙 * =路径
int cost; // 代价权重
};
struct Compare
{
bool operator()(const Node &a, const Node &b)
{
return a.cost > b.cost; // 小根堆
}
};
bool check(Node &node)
{
return node.x == row - 1 && node.y == col - 1;
}
int row;
int col;
Node **pMaze;
vector<vector<int>> dist; // 最小代价数组（Dijkstra核心）
vector<Node> path; // 记录bfs时，节点的行走信息
};
这里代码的核心逻辑在于：
- 用距离数组 dist 记录起点到每个点的最小代价
- 用优先队列（小根堆）priority_queue 每次选代价最小的点扩展
- 用前驱数组 path 记录路径（与 BFS 完全一样）
- 不能走回头路，只更新更短的路径
代码中，记录从起点到当前节点的代价变量是dist二维数组，它的起始值设置的是INT_MAX，这是一个技巧。
// 新代价=当前代价+下一个节点的代价
int newCost = dist[x][y] + pMaze[nx][ny].cost;
if (newCost < dist[nx][ny])
{
dist[nx][ny] = newCost;
path[nx * row + ny] = top; // 记录节点的行走信息
q.push(pMaze[nx][ny]);
}- dist[x][y]表示从起点走到当前节点x,y的最小真实代价。这是已经确定的最优解
- pMaze[nx][ny].cost是从当前节点，走到下一个节点nx,ny的代价。
- newCost是从起点->当前节点->下一个接地那的总代价，也是新路线的代价
- dist[nx][ny]是之前没有走过，或已经走过的从起点到下一个节点nx,ny的最小代价
- 当第一次到达nx和ny时，一定会更新，因为它是无穷大
- 如果之前通过其它路径到过nx和ny，如果当前的路线比这个代价更小，就更新为当前路径。
在DFS和BFS中，都需要判断State里面的方向来判断该方向是否能走。但在Dijkstra方法中，这些都以最小代价的方法来实现了。比如在BFS中，代码：
if (pMaze[x][y].state[RIGHT]) { ... }判断向右边的状态，是否能否。然后如果可以走，还需要设置state的状态回false，防止走回头路。但在Dijkstra中，判断能不能走只看2个条件：
- 是不是墙，即val==1的不能走。
- 新路径的代价是否更小，即newCost<dist[nx][ny]。
只要不是墙，且路径更优就能走。
另外，在DFS和BFS中，防止走回头路的策略是，探测完一个方向之后，将该方向以及探测的方向的反方向都设置为false，防止走回头路，比如：
pMaze[x][y].state[RIGHT] = false;
pMaze[x][y+1].state[LEFT] = false;但在Dijkstra中并不需要，原因有：
首先：dist数组自动拒绝更差的路径：
if (newCost < dist[nx][ny])如果走回头路，新代价一定会大于原来的代码，上述不等式不成立。
其次：小根堆能保证一个点被弹出，就永远得到了最小代价，不可能再次被更新。
最后：即使被重复入队，也会被下面这句过滤：
if (dist[x][y] < u.cost) continue;使用方法如下：
int main()
{
cout << "请输入迷宫的行列数，例如：10 10：";
int row, col, data;
cin >> row >> col;
Maze maze(row, col); //
cout << "请输入迷宫的路径信息(0表示可以走，1表示不能走)" << endl;
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
cin >> data;
if ( data == 1)
{
maze.initNode(i, j, data);//不能走，墙，权重为默认1
}
else
{
maze.initNode(i, j, 0, data);//可以走，否则权重为data
}
}
}
cout << "======================" << endl;
maze.searchMazePath();
maze.showMazePath();
cout << endl;
return 1;
}输出结果如下：
请输入迷宫的行列数，例如：10 10：6 6
请输入迷宫的路径信息(0表示可以走，1表示不能走)
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 0 0 0 0
======================
* * 1 1 1 1
1 * 0 0 0 1
1 * 1 1 0 1
1 * 0 0 0 1
1 * 1 1 1 1
1 * * * * *
请输入迷宫的行列数，例如：10 10：6 6
请输入迷宫的路径信息(0表示可以走，1表示不能走)
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 0 1
1 0 0 0 0 0
======================
* * 1 1 1 1
1 * 0 0 0 1
1 * 1 1 0 1
1 * * * * 1
1 1 1 1 * 1
1 0 0 0 * * 可以看到，这里的路径跟BFS是完全一样的。
当我把下面这条路径的权重变大，它就会自动跳回到上一条路径：
请输入迷宫的行列数，例如：10 10：6 6
请输入迷宫的路径信息(0表示可以走，1表示不能走)
0 0 1 1 1 1
1 0 0 0 0 1
1 0 1 1 0 1
1 0 3 0 0 1
1 1 1 1 0 1
1 0 0 0 0 0
======================
* * 1 1 1 1
1 * * * * 1
1 0 1 1 * 1
1 0 0 0 * 1
1 1 1 1 * 1
1 0 0 0 * * 五、A*算法
如前所述，Dijkstra算法可以看作是有权版本的BFS，他们有一些缺点：
- BFS和Dijkstra都是一层一层往外扩展搜索，类似水波纹，在很多搜索方向根本远离终点，浪费算力。
- 在大的迷宫里，Dijkstra要跑遍半个地图才能找到重点，搜索的范围大，效率低。
- Dijkstra只知道代价最小，他不知道目标终点的位置，没有“方向感”
为了解决Dijkstra算法的以上问题，A*算法应运而生，它既保留了最短路径的特性，又提高了搜索效率，它的做法是在原来的最小代价基础上，增加了启发函数（huristic fuction）：
f(n) = g(n) + h(n)上述公式中：
- g(n)：起点走到当前点的代价（= Dijkstra 的代价）
- h(n)：当前点 预估 到终点的代价（启发函数，A* 核心）
- f(n)：综合优先级，越小越优先走
在迷宫算法里，h(n)可以使用曼哈顿距离：
h = |x - endX| + |y - endY|就是“横向差+纵向差”，非常快。
代码实现如下：
#include <iostream>
#include <mutex>
#include <string>
#include <memory>
#include <queue>
#include <vector>
using namespace std;
const int WAY_NUM = 4;
// 四个方向偏移量,右、下、左、上
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
class Maze
{
public:
Maze(int c, int r) : col(c), row(r)
{
pMaze = new Node *[row];
for (size_t i = 0; i < row; ++i)
{
pMaze[i] = new Node[col];
}
dist.resize(row, vector<int>(col, INT_MAX));
path.resize(row, vector<Node>(col));
}
// 析构函数：释放内存
~Maze()
{
for (size_t i = 0; i < row; i++)
{
delete[] pMaze[i];
}
delete[] pMaze;
}
void initNode(int x, int y, int val, int cost = 1)
{
pMaze[x][y].x = x;
pMaze[x][y].y = y;
pMaze[x][y].val = val;
pMaze[x][y].cost = cost;
}
// 曼哈顿距离（A*核心启发函数）
int heuristic(int x, int y)
{
int ex = row - 1;
int ey = col - 1;
return abs(x - ex) + abs(y - ey);
}
void searchMazePath()
{
if (pMaze[0][0].val == 1)
{
return;
}
// 优先队列（小根堆）
priority_queue<Node, vector<Node>, Compare> q;
Node start = pMaze[0][0];
start.g = 0;
start.h = heuristic(0, 0);
start.f = start.g + start.h;
dist[0][0] = 0;
q.push(start);
while (!q.empty())
{
Node top = q.top();
q.pop();
int x = top.x;
int y = top.y;
// 已经找到右下角，得到迷宫路径
if (x == row - 1 && y == col - 1)
{
return;
}
// 旧代价，跳过
if (dist[x][y] < top.g)
{
continue;
}
for (int d = 0; d < WAY_NUM; d++)
{
int nx = x + dx[d];
int ny = y + dy[d];
if (nx < 0 || nx >= row || ny < 0 || ny >= col)
{
continue; // 越界
}
if (pMaze[nx][ny].val == 1)
{
continue; // 墙
}
// 新代价=当前代价+下一个节点的代价
int newG = dist[x][y] + pMaze[nx][ny].cost;
if (newG < dist[nx][ny])
{
dist[nx][ny] = newG;
path[nx][ny] = top; // 记录节点的行走信息
Node nextNode = pMaze[nx][ny];
nextNode.g = newG;
nextNode.h = heuristic(nx, ny);
nextNode.f = nextNode.g + nextNode.h;
q.push(nextNode);
}
}
}
}
void showMazePath()
{
int x = row - 1;
int y = col - 1;
// 如果出口的前驱节点不存在 → 没路径
if (dist[x][y] == INT_MAX)
{
cout << "Dijkstra：找不到迷宫路径！" << endl;
return;
}
for (;;)
{
pMaze[x][y].val = '*';
if (x == 0 && y == 0)
{
break;
}
Node node = path[x][y];
x = node.x;
y = node.y;
}
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
if (pMaze[i][j].val == '*')
{
cout << "* ";
}
else
{
cout << pMaze[i][j].val << " ";
}
}
cout << endl;
}
}
private:
struct Node
{
int x;
int y;
int val; // 0=路 1=墙 * =路径
int cost; // 代价（权重）
int g, h, f; // g:已走代价 h:预估代价 f:总优先级
Node(int x_, int y_, int val_, int cost_) : x(x_), y(y_), val(val_), cost(cost_) {}
Node() : x(-1), y(-1), val(0), g(0), h(0), f(0) {}
};
// 小根堆：f值最小优先
struct Compare
{
bool operator()(const Node &a, const Node &b)
{
return a.f > b.f;
}
};
bool check(Node &node)
{
return node.x == row - 1 && node.y == col - 1;
}
int row;
int col;
Node **pMaze;
vector<vector<int>> dist; // 最小代价数组（Dijkstra核心）
vector<vector<Node>> path; // 前驱节点
};使用方法如下：
int main()
{
cout << "请输入迷宫的行列数，例如：10 10：";
int row, col, data;
cin >> row >> col;
Maze maze(row, col); //
cout << "请输入迷宫的路径信息(0表示可以走，1表示不能走)" << endl;
for (size_t i = 0; i < row; ++i)
{
for (size_t j = 0; j < col; ++j)
{
cin >> data;
if (data == 1)
{
maze.initNode(i, j, data); // 不能走，墙，权重为默认1
}
else
{
maze.initNode(i, j, 0, data); // 可以走，否则权重为data
}
}
}
cout << "======================" << endl;
maze.searchMazePath();
maze.showMazePath();
cout << endl;
return 1;
}六、四种算法的可视化对比
前面已经分别少了DFS、BFS、Dijkstra以及A Start算法以及各自的特点，下面这个程序可以动态显示各种算法之间的区别：
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <tuple>
#include <climits>
#include <cmath>
#include <windows.h>
using namespace std;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
#define COL_DEFAULT 7
#define COL_VISITED 11
#define COL_PATH 10
#define COL_SAND 6
#define COL_MUD 4
struct Node {
int x, y;
int val;
int cost;
bool visited;
bool isPath;
Node()
: x(-1), y(-1), val(1), cost(1), visited(false), isPath(false) {}
Node(int x_, int y_, int v_, int c_)
: x(x_), y(y_), val(v_), cost(c_), visited(false), isPath(false) {}
};
void setColor(int c) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), c);
}
class Maze {
public:
int row, col;
Node** pMaze;
vector<vector<pair<int, int>>> prev;
Maze(int r, int c) : row(r), col(c) {
pMaze = new Node * [row];
for (int i = 0; i < row; ++i)
pMaze[i] = new Node[col];
prev.resize(row, vector<pair<int, int>>(col, { -1,-1 }));
}
~Maze() {
for (int i = 0; i < row; ++i) delete[] pMaze[i];
delete[] pMaze;
}
void setNode(int x, int y, int val, int cost) {
pMaze[x][y] = Node(x, y, val, cost);
}
void showTip() {
setColor(COL_DEFAULT);
cout << "图例：";
cout << "#=墙 ";
cout << "O=平地 ";
cout << "~=沙地 ";
cout << "=泥地 ";
setColor(COL_VISITED); cout << "蓝色=搜索过 ";
setColor(COL_PATH); cout << "绿色=最终路径\n";
setColor(COL_DEFAULT);
}
void draw(const string& title) {
system("cls");
cout << "===== " << title << " =====\n";
showTip();
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
char ch = '?';
int color = COL_DEFAULT;
if (pMaze[i][j].val == 1) {
ch = '#';
color = COL_DEFAULT;
} else {
// 平地用 O，无编译错误，显示清晰
if (pMaze[i][j].cost == 1)
ch = 'O';
else if (pMaze[i][j].cost == 3)
ch = '~';
else if (pMaze[i][j].cost == 5)
ch = '=';
if (pMaze[i][j].isPath) {
color = COL_PATH;
} else if (pMaze[i][j].visited) {
color = COL_VISITED;
} else {
if (pMaze[i][j].cost == 3)
color = COL_SAND;
else if (pMaze[i][j].cost == 5)
color = COL_MUD;
else
color = COL_DEFAULT;
}
}
setColor(color);
cout << ch << ' ';
}
cout << '\n';
}
setColor(COL_DEFAULT);
Sleep(25);
}
void reset() {
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
pMaze[i][j].visited = false;
pMaze[i][j].isPath = false;
prev[i][j] = { -1,-1 };
}
}
}
// DFS
bool dfs(int x, int y) {
if (x == row - 1 && y == col - 1) return true;
if (pMaze[x][y].val == 1 || pMaze[x][y].visited) return false;
pMaze[x][y].visited = true;
draw("DFS 搜索中");
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < row && ny < col) {
if (!pMaze[nx][ny].visited && pMaze[nx][ny].val == 0) {
prev[nx][ny] = { x, y };
if (dfs(nx, ny))
return true;
}
}
}
return false;
}
void dfsDrawPath() {
int x = row - 1, y = col - 1;
while (x != -1 && y != -1) {
pMaze[x][y].isPath = true;
auto p = prev[x][y];
x = p.first;
y = p.second;
}
draw("DFS 结果");
}
// BFS
void bfs() {
queue<pair<int, int>> q;
vector<vector<pair<int, int>>> prev(row, vector<pair<int, int>>(col, { -1,-1 }));
q.push({ 0,0 });
pMaze[0][0].visited = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
draw("BFS 搜索中");
if (x == row - 1 && y == col - 1) break;
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < row && ny < col) {
if (!pMaze[nx][ny].visited && pMaze[nx][ny].val == 0) {
pMaze[nx][ny].visited = true;
prev[nx][ny] = { x,y };
q.push({ nx,ny });
}
}
}
}
int x = row - 1, y = col - 1;
while (x != -1) {
pMaze[x][y].isPath = true;
auto p = prev[x][y];
x = p.first; y = p.second;
}
draw("BFS 结果");
}
// Dijkstra
void dijkstra() {
using Tuple = tuple<int, int, int>;
priority_queue<Tuple, vector<Tuple>, greater<>> q;
vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
vector<vector<pair<int, int>>> prev(row, vector<pair<int, int>>(col, { -1,-1 }));
dist[0][0] = 0;
q.emplace(0, 0, 0);
while (!q.empty()) {
auto [c, x, y] = q.top(); q.pop();
if (pMaze[x][y].visited) continue;
pMaze[x][y].visited = true;
draw("Dijkstra 搜索中");
if (x == row - 1 && y == col - 1) break;
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < row && ny < col && pMaze[nx][ny].val == 0) {
int newCost = c + pMaze[nx][ny].cost;
if (newCost < dist[nx][ny]) {
dist[nx][ny] = newCost;
prev[nx][ny] = { x,y };
q.emplace(newCost, nx, ny);
}
}
}
}
int x = row - 1, y = col - 1;
while (x != -1) {
pMaze[x][y].isPath = true;
auto p = prev[x][y];
x = p.first; y = p.second;
}
draw("Dijkstra 结果");
}
// A*
void astar() {
using Tuple = tuple<int, int, int, int>;
priority_queue<Tuple, vector<Tuple>, greater<>> q;
vector<vector<int>> dist(row, vector<int>(col, INT_MAX));
vector<vector<pair<int, int>>> prev(row, vector<pair<int, int>>(col, { -1,-1 }));
auto h = [&](int x, int y) {
return abs(x - (row - 1)) + abs(y - (col - 1));
};
dist[0][0] = 0;
q.emplace(h(0, 0), 0, 0, 0);
while (!q.empty()) {
auto [f, g, x, y] = q.top(); q.pop();
if (pMaze[x][y].visited) continue;
pMaze[x][y].visited = true;
draw("A* 搜索中");
if (x == row - 1 && y == col - 1) break;
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && ny >= 0 && nx < row && ny < col && pMaze[nx][ny].val == 0) {
int newG = g + pMaze[nx][ny].cost;
if (newG < dist[nx][ny]) {
dist[nx][ny] = newG;
prev[nx][ny] = { x,y };
q.emplace(newG + h(nx, ny), newG, nx, ny);
}
}
}
}
int x = row - 1, y = col - 1;
while (x != -1) {
pMaze[x][y].isPath = true;
auto p = prev[x][y];
x = p.first; y = p.second;
}
draw("A* 结果");
}
};
int map[16][16] = {
{0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,2,2,0,0,0,0,0,1},
{1,0,1,1,1,1,0,1,3,3,0,1,1,1,0,1},
{1,0,1,0,0,0,0,1,3,3,0,0,0,1,0,1},
{1,0,1,0,1,1,1,1,0,0,1,1,0,1,0,1},
{1,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1},
{1,0,1,0,1,0,1,1,1,1,1,1,0,1,0,1},
{1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1},
{1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1},
{1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1},
{1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},
};
int main() {
Maze maze(16, 16);
for (int i = 0; i < 16; ++i) {
for (int j = 0; j < 16; ++j) {
if (map[i][j] == 1)
maze.setNode(i, j, 1, 0);
else if (map[i][j] == 2)
maze.setNode(i, j, 0, 3);
else if (map[i][j] == 3)
maze.setNode(i, j, 0, 5);
else
maze.setNode(i, j, 0, 1);
}
}
cout << "16×16 迷宫寻路对比\n";
cout << "依次演示：DFS → BFS → Dijkstra → A*\n按回车开始...";
cin.get();
maze.reset();
maze.dfs(0, 0);
maze.dfsDrawPath();
cout << "\nDFS 结束，回车继续 BFS..."; cin.get();
maze.reset();
maze.bfs();
cout << "\nBFS 结束，回车继续 Dijkstra..."; cin.get();
maze.reset();
maze.dijkstra();
cout << "\nDijkstra 结束，回车继续 A*..."; cin.get();
maze.reset();
maze.astar();
cout << "\n全部演示完成！\n";
return 0;
}
下面这个是DFS的输出结果：
BFS的结果：
Dijkstra的结果：
A Star的结果：
下面是对这几种算法的简单比较：
