1、前言
我们都知道，一般二维数组都可以用 dfs 或者 bfs 来遍历，但是往往求最短路径是 bfs，这是为啥呢？因为 dfs 不好计算路径，bfs 初始将起点放入队列，然后依次扩散，很容易计算最短路径。一个简单的 bfs 求最短路径如下。
题目描述：假设有一个二维矩阵（二维字符数组），矩阵的字符 s 表示小明的起点，字符 e 表示小明的终点，字符 1 代表可以走，字符 0 代表有障碍物。请找到一个从 s 到 e 的最短路径。
这道题就可以用 bfs 来做，先把起点 s 的位置放入队列，然后慢慢扩散，队列每次清完一组长度就 + 1。
public class ShortPath {
public int shortPath(char[][] path){
if(path == null || path.length == 0 || path[0].length == 0){
return 0;
}
Queue<int[]> queue = new LinkedList<>();
int m = path.length, n = path[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(path[i][j] == 's'){
queue.add(new int[]{i, j});
}
}
}
// 记录添加的位置，防止重复添加
boolean[][] visited = new boolean[m][n];
int step = 0;
while (!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] position = queue.poll();
int row = position[0], column = position[1];
if(path[row][column] == 'e'){
return step;
}
// ****************************************************
// 或者看到其他的一些做法，将上下左右封装到一个二维数组中遍历，先加后尝试
// 上
if(row - 1 >= 0 && column < n && !visited[row - 1][column] && path[row - 1][column] != '0'){
visited[row - 1][column] = true;
queue.add(new int[]{row - 1, column});
}
// 下
if(row + 1 < m && column < n && !visited[row + 1][column] && path[row + 1][column] != '0'){
visited[row + 1][column] = true;
queue.add(new int[]{row + 1, column});
}
// 左
if(row < m && column - 1 >= 0 && !visited[row][column - 1] && path[row][column - 1] != '0'){
visited[row][column - 1] = true;
queue.add(new int[]{row, column - 1});
}
// 右
if(row < m && column + 1 < n && !visited[row][column + 1] && path[row][column + 1] != '0'){
visited[row][column + 1] = true;
queue.add(new int[]{row, column + 1});
}
}
step++;
}
return -1;
}
public static void main(String[] args) {
char[][] path = {
{'1', '1', '0', '0', '1', '1'},
{'0', 's', '1', '1', '1', '0'},
{'1', '0', '1', '0', '1', '1'},
{'1', '0', '1', '0', '1', '1'},
{'1', '1', '1', '0', '0', '1'},
{'0', '1', '1', '1', 'e', '1'},
};
System.out.println(new ShortPath().shortPath(path));
}
}
bfs 算法虽然能解决走迷宫问题，但是因为它太慢了，因为它的时间复杂度为 O(n^2)（还有一点要注意，bfs 可以多源开始，如果是求多个点到某一个点的最短值，可以把多个点先加入队列，然后一起遍历）。
所以一般使用 dijkstra 算法或者 A* 算法来求最短路径。
2、dijkstra 算法
dijkstra 算法的思路很简单，假设有一张路径图：
路径图
前置条件：首先有一个 dist 数组，初始化为起始节点到其他节点的距离，不可达表示为 +∞。使用一个 visited 数组，表示以某个节点作为中间节点是否访问过。middle 记录最短路径节点的编号，minDist 记录最小值。
过程：
- 1）首先循环 dist 数组，找到节点 i 到其他节点的最小值（已经作为 middle 节点的会被标记，会被除外），记录最小值与最小值点编号
- 2）然后以该 middle 节点作为起点，计算节点 i 到其他节点的值（已经作为 middle 节点的会被标记，会被除外）是否大于起始节点到 middle 节点 + middle 节点到其他节点的和，如果大于，说明又更近的路，把 dist 中该值替换为较小的值。
- 3）直到所有节点结束。
代码如下：
public class Dijkstra {
// graph 是一个 n * n 的矩阵，start 表示起始顶点是啥
public int[] dijstra(int[][] graph, int start){
int n = graph.length;
// 标记已作为中间节点完成访问的节点
boolean[] visited = new boolean[n];
// 存储从起始节点到其他顶点的最短路径
int[] dist = new int[n];
// 初始化为起始顶点到其他节点的距离
for(int i = 0; i < n; i++){
dist[i] = graph[start][i];
}
visited[start] = true;
for(int i = 0; i < n; i++){
int minDist = Integer.MAX_VALUE;
// 存储最短距离节点的编号
int middle = 0;
for(int j = 0; j < n; j++){
if(!visited[j] && dist[j] < minDist){
minDist = dist[j];
middle = j;
}
}
// 以 middle 为中间节点，再循环遍历其他节点
for(int j = 0; j < n; j++){
// 如果当前遍历的节点未被作为中间节点，并且从起始点到 j 的距离 dist[j] 大于从起始点到 middle 与从 middle 到 j 的距离和
if(!visited[j] && dist[j] > dist[middle] + graph[middle][j]){
// 更新起始节点到 j 的距离 dist[j]，更新为起始节点到 middle 与 middle 到 j 的距离和
dist[j] = dist[middle] + graph[middle][j];
}
}
visited[middle] = true;
}
return dist;
}
public static void main(String[] args) {
// +∞ 用 Integer.MAX_VALUE / 2 防止溢出
// 假设 0，1，2，3，4，5 分别表示：北京、天津、郑州、济南、长沙、海南
int[][] graph = {
{0, 100, 1200, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2},
{100, 0, 900, 300, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2},
{1200, 900, 0, 400, 500, Integer.MAX_VALUE / 2},
{Integer.MAX_VALUE / 2, 300, 400, 0, 1300, 1400},
{Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 500, 1300, 0, 1500},
{Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, Integer.MAX_VALUE / 2, 1400, 1500, 0}
};
int[] res = new Dijkstra().dijstra(graph, 0);
System.out.println();
}
}
这种 O(n^2) 求到所有点的最短路径很方便，但是这个可以使用堆优化，堆优化后基本上流程跟 A* 差不多，只不过 A* 的代价函数不一样。
流程：
- 1、将源点加入堆，并调整堆。
- 2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
- 3、处理与u相邻的，未被访问过的，满足三角不等式的顶点。若该点在堆里，更新距离，并调整该元素在堆中的位置；若该点不在堆里，加入堆，更新堆。
- 4、若取到的u为终点，结束算法；否则重复步骤2、3。
/**
* @author xushu
* @create 7/12/21 10:43 AM
* @desc 堆优化后，有点像 A* 算法
*/
public class DijkstraUsingHeap {
//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连
public int dijkstra(int src, int dst, int[][] graph){
int n = graph.length;
boolean[] visited = new boolean[n];
PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.cost - o2.cost;
}
});
//将起点加入pq
pq.add(new Node(src, 0));
while(!pq.isEmpty()){
Node t = pq.poll();
//当前节点是终点，即可返回最短路径
if(t.node == dst) return t.cost;
//若当前节点已遍历过，跳过当前节点
if(visited[t.node]) continue;
//将当前节点标记成已遍历
visited[t.node] = true;
for(int i = 0; i < n; i++){
if(!visited[i]){
pq.add(new Node(i, t.cost + graph[t.node][i]));
}
}
}
return -1;
}
//定义一个存储节点和离起点相应距离的数据结构
class Node {
/**
* 保存位置
*/
public int node;
/**
* 保存累加的代价
*/
public int cost;
public Node()
{
}
public Node(int node, int cost)
{
this.node = node;
this.cost = cost;
}
}
public static void main(String[] args) {
final int M = 10000; // 代表正无穷
// 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
// A -> A 距离为0, 常量M 为正无穷
int[][] graph = {
{0, 4, M, 2, M},
{4, 0, 4, 1, M},
{M, 4, 0, 1, 3},
{2, 1, 1, 0, 7},
{M, M, 3, 7, 0}
};
int start = 0, des = 3;
DijkstraUsingHeap shortestPath = new DijkstraUsingHeap();
int shortPath = shortestPath.dijkstra(start, des, graph);
System.out.println("从" + start + "出发到" + des + "的最短距离为：" + shortPath);
}
}
3、A* 算法
A* 算法最重要的是：F = G + H，F 表示选取某一个格子的代价，G 表示走上下左右的（可能包括斜边的代价），H 表示走的那个格子到终点的距离，一般用曼哈顿距离，即 path = |X_i - X_end| + |Y_i - Y_end|。
A* 算法比较类似于 dfs 的思路，只不过 dfs 是全面开花进行扩散，A* 是选择代价即 F 最小的，然后根据此选择进行扩散。
代码如下：
public class AStar {
public static class Node {
public int x;
public int y;
public int F;
public int G;
public int H;
// 判断是否是上下左右的点
public boolean isStep;
public Node parent;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public Node(int x, int y, boolean isStep) {
this.x = x;
this.y = y;
this.isStep = isStep;
}
public void calcF() {
this.F = this.G + this.H;
}
}
public static final int[][] NODES = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
public static final int STEP = 10;
// 勾股定理，c = sqrt(a^2 + b^2)
public static final int OBLIWUE = 14;
private ArrayList<Node> openList = new ArrayList<Node>();
private ArrayList<Node> closeList = new ArrayList<Node>();
public Node findMinFNodeInOpenList() {
Node tempNode = openList.get(0); // 先以第一个元素的F为最小值，然后遍历openlist的所有值，找出最小值
for (Node node : openList) {
if (node.F < tempNode.F) {
tempNode = node;
}
}
return tempNode;
}
// 考虑周围节点的时候，就不把节点值为1的节点考虑在内，所以自然就直接避开了障碍物
public ArrayList<Node> findNeighborNodes(Node currentNode) {
ArrayList<Node> arrayList = new ArrayList<Node>();
// 上
int topX = currentNode.x;
int topY = currentNode.y - 1;
// canReach方法确保下标没有越界 exists方法确保此相邻节点不存在于closeList中，也就是之前没有遍历过
if (canReach(topX, topY) && !exists(closeList, topX, topY)) {
arrayList.add(new Node(topX, topY, true));
}
// 下
int bottomX = currentNode.x;
int bottomY = currentNode.y + 1;
if (canReach(bottomX, bottomY) && !exists(closeList, bottomX, bottomY)) {
arrayList.add(new Node(bottomX, bottomY, true));
}
// 左
int leftX = currentNode.x - 1;
int leftY = currentNode.y;
if (canReach(leftX, leftY) && !exists(closeList, leftX, leftY)) {
arrayList.add(new Node(leftX, leftY, true));
}
// 右
int rightX = currentNode.x + 1;
int rightY = currentNode.y;
if (canReach(rightX, rightY) && !exists(closeList, rightX, rightY)) {
arrayList.add(new Node(rightX, rightY, true));
}
// 左上
int leftUpX = currentNode.x - 1;
int leftUpY = currentNode.y - 1;
if (canReach(leftUpX, leftUpY) && !exists(closeList, leftUpX, leftUpY)) {
arrayList.add(new Node(leftUpX, leftUpY, false));
}
// 左下
int leftDownX = currentNode.x + 1;
int leftDownY = currentNode.y - 1;
if (canReach(leftDownX, leftDownY) && !exists(closeList, leftDownX, leftDownY)) {
arrayList.add(new Node(leftDownX, leftDownY, false));
}
// 右上
int rightUpX = currentNode.x - 1;
int rightUpY = currentNode.y + 1;
if (canReach(rightUpX, rightUpY) && !exists(closeList, rightUpX, rightUpY)) {
arrayList.add(new Node(rightUpX, rightUpY, false));
}
// 右下
int rightDownX = currentNode.x + 1;
int rightDownY = currentNode.y + 1;
if (canReach(rightDownX, rightDownY) && !exists(closeList, rightDownX, rightDownY)) {
arrayList.add(new Node(rightDownX, rightDownY, false));
}
return arrayList;
}
public boolean canReach(int x, int y) {
if (x >= 0 && x < NODES.length && y >= 0 && y < NODES[0].length) {
return NODES[x][y] == 0; // 原来是在这里避过障碍物的啊。。如果节点值不为0，说明不可到达。
}
return false;
}
public Node findPath(Node startNode, Node endNode) {
// 把起点加入 open list
openList.add(startNode);
while (openList.size() > 0) {
// 遍历 open list ，查找 F值最小的节点，把它作为当前要处理的节点
Node currentNode = findMinFNodeInOpenList();
// F值最小的节点从open list中移除
openList.remove(currentNode);
// 把这个节点移到 close list，closelist就是存储路径的链表
closeList.add(currentNode);
// 查找不存在于close list当中的周围节点（考虑斜边的邻居）
ArrayList<Node> neighborNodes = findNeighborNodes(currentNode);
// openlist其实就是存储的外围的节点集合
for (Node node : neighborNodes) {// 总之要把邻居节点添加进openlist当中
if (exists(openList, node)) { // 如果邻居节点在openlist当中
foundPoint(currentNode, node);
} else {
// 如果邻居节点不在openlist中，那就添加进openlist
notFoundPoint(currentNode, endNode, node);
}
}
// 如果在openlist中找到了终点，那么就说明已经找到了路径，返回终点
if (find(openList, endNode) != null) {
return find(openList, endNode);
}
}
return find(openList, endNode);
}
// 此种情况就是发现周围的F值最小的节点是之前已经遍历过了的，所以这个节点的G,H,F值都是已经计算过了的
// 此时H值肯定不会变，所以要比较G值，如果现在的G值比之前的小，说明现在的路径更优
// 接着就重置此节点的父指针，G值和F值
private void foundPoint(Node tempStart, Node node) {
int G = calcG(node);
if (G < node.G) {
node.parent = tempStart;
node.G = G;
node.calcF();
}
}
// 这种情况是之前没有计算过此节点的值，所以在这里要计算一遍G,H,F值，然后确认父指针指向，然后加入openlist当中
private void notFoundPoint(Node parentStart, Node end, Node node) {
node.parent = parentStart;
node.G = calcG(node);
node.H = calcH(end, node);
node.calcF();
openList.add(node);
}
private int calcG(Node node) {
int G = STEP;
if(!node.isStep){
G = OBLIWUE;
}
int parentG = node.parent != null ? node.parent.G : 0;
return G + parentG;
}
// 这是曼哈顿距离计算公式，可以替换成别的
private int calcH(Node end, Node node) {
int step = Math.abs(node.x - end.x) + Math.abs(node.y - end.y);
return step * STEP;
}
public static Node find(List<Node> nodes, Node point) {
for (Node n : nodes)
if ((n.x == point.x) && (n.y == point.y)) {
return n;
}
return null;
}
public static boolean exists(List<Node> nodes, Node node) {
for (Node n : nodes) {
if ((n.x == node.x) && (n.y == node.y)) {
return true;
}
}
return false;
}
public static boolean exists(List<Node> nodes, int x, int y) {
for (Node n : nodes) {
if ((n.x == x) && (n.y == y)) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Node startNode = new Node(5, 1);
Node endNode = new Node(5, 5);
Node parent = new AStar().findPath(startNode, endNode);// 返回的是终点，但是此时父节点已经确立，可以追踪到开始节点
for (int i = 0; i < NODES.length; i++) {
for (int j = 0; j < NODES[0].length; j++) {
System.out.print(NODES[i][j] + ", ");
}
System.out.println();
}
ArrayList<Node> arrayList = new ArrayList<Node>();
while (parent != null) {// 遍历刚才找到的路径。没问题
// System.out.println(parent.x + ", " + parent.y);
arrayList.add(new Node(parent.x, parent.y));
parent = parent.parent;
}
System.out.println("\n");
for (int i = 0; i < NODES.length; i++) {
for (int j = 0; j < NODES[0].length; j++) {
if (exists(arrayList, i, j)) {// 把路径经过的点用@表示
System.out.print("@, ");
} else {
System.out.print(NODES[i][j] + ", ");
}
}
System.out.println();
}
}
}
4、后记
关于 bfs 怎么追踪到路径呢？答案就是有一个 node，它有一个 pre 指针，在到终点的过程中，每次将它的 parent 赋值给 pre，然后到终点的时候，返回终点的 node，就能通过终点追踪到起点的路径。
public class ShortPath {
public Path shortPath(char[][] path){
if(path == null || path.length == 0 || path[0].length == 0){
return null;
}
Queue<Path> queue = new LinkedList<>();
int m = path.length, n = path[0].length;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(path[i][j] == 's'){
queue.add(new Path(i, j));
}
}
}
// 记录添加的位置，防止重复添加
boolean[][] visited = new boolean[m][n];
int step = 0;
while (!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
Path position = queue.poll();
int row = position.x, column = position.y;
if(path[row][column] == 'e'){
return position;
}
// ****************************************************
// 或者看到其他的一些做法，将上下左右封装到一个二维数组中遍历，先加后尝试
// 上
if(row - 1 >= 0 && column < n && !visited[row - 1][column] && path[row - 1][column] != '0'){
visited[row - 1][column] = true;
Path p = new Path(row - 1, column);
p.pre = position;
queue.add(p);
}
// 下
if(row + 1 < m && column < n && !visited[row + 1][column] && path[row + 1][column] != '0'){
visited[row + 1][column] = true;
Path p = new Path(row + 1, column);
p.pre = position;
queue.add(p);
}
// 左
if(row < m && column - 1 >= 0 && !visited[row][column - 1] && path[row][column - 1] != '0'){
visited[row][column - 1] = true;
Path p = new Path(row, column - 1);
p.pre = position;
queue.add(p);
}
// 右
if(row < m && column + 1 < n && !visited[row][column + 1] && path[row][column + 1] != '0'){
visited[row][column + 1] = true;
Path p = new Path(row, column + 1);
p.pre = position;
queue.add(p);
}
}
step++;
}
return null;
}
public static void main(String[] args) {
char[][] path = {
{'1', '1', '0', '0', '1', '1'},
{'0', 's', '1', '1', '1', '0'},
{'1', '0', '1', '0', '1', '1'},
{'1', '0', '1', '0', '1', '1'},
{'1', '1', '1', '0', '0', '1'},
{'0', '1', '1', '1', 'e', '1'},
};
Path parent = new ShortPath().shortPath(path);
ArrayList<Path> arrayList = new ArrayList<Path>();
while (parent != null) {// 遍历刚才找到的路径。没问题
// System.out.println(parent.x + ", " + parent.y);
arrayList.add(new Path(parent.x, parent.y));
parent = parent.pre;
}
System.out.println("\n");
for (int i = 0; i < path.length; i++) {
for (int j = 0; j < path[0].length; j++) {
if (exists(arrayList, i, j)) {// 把路径经过的点用@表示
System.out.print("@, ");
} else {
System.out.print(path[i][j] + ", ");
}
}
System.out.println();
}
}
public static boolean exists(List<Path> nodes, int x, int y) {
for (Path n : nodes) {
if ((n.x == x) && (n.y == y)) {
return true;
}
}
return false;
}
}
