java - 使用 BFS 从起点到终点的最短路径
问题描述
S
如果从表示为endpoint的给定起点存在,我想显示最短路径E
。我有一个矩阵,其值0
指示没有路径并1
指示访问的有效路径。我可以按行和按列访问,但不能以对角方式访问。现在使用 BFS,我可以使用以下代码将最短路径值作为整数:
public static void main(String[] args) {
int r = findShortestPathBFS(new char[][] { "0001110011".toCharArray(), "1111011110".toCharArray(),
"0110001010".toCharArray(), "S010101011".toCharArray(), "1110111E01".toCharArray() }, 3, 0);
System.out.println(r);
}
private static int findShortestPathBFS(char arr[][], int startX, int startY) {
if (arr[startX][startY] == 'E')
return 0;
int moveX[] = new int[] { 0, 0, 1, -1 };
int moveY[] = new int[] { 1, -1, 0, 0 };
boolean visited[][] = new boolean[arr.length][arr[0].length];
Queue<QNode> qNodes = new LinkedList<>();
qNodes.add(new QNode(startX, startY, 0));
while (!qNodes.isEmpty()) {
QNode currNode = qNodes.remove();
int currX = currNode.x;
int currY = currNode.y;
int currDistance = currNode.distance;
visited[currX][currY] = true;
// System.out.println(arr[currX][currY]);
if (arr[currX][currY] == 'E')
return currDistance;
for (int i = 0; i < moveX.length; i++) {
int newX = currX + moveX[i];
int newY = currY + moveY[i];
if (newX >= 0 && newX < arr.length && newY >= 0 && newY < arr[0].length && !visited[newX][newY]
&& arr[newX][newY] != '0') {
qNodes.add(new QNode(newX, newY, currDistance + 1));
}
}
}
return -1;
}
private static class QNode {
int x;
int y;
int distance;
QNode(int x, int y, int distance) {
this.x = x;
this.y = y;
this.distance = distance;
}
}
在此示例中,输入为:
0001110011
1111011110
0110001010
S010101011
1110111E01
[3,0]
是我的起点,[4,7]
是我有价值的目的地E
上面的代码打印16
为最短路径。not exists
但如果存在或无法到达目的地,我想打印这样的实际路径。
上述代码的预期输出:
000***0011
11**0**110
01*000*010
S0*010*011
***011*E01
在这里,我想用有效的路径路线再次打印矩阵*
。如何在我的代码中实现这一点,还是有更好的方法来解决这个问题?
解决方案
您可以在您的类 QNode 中有一个名为 prev 的字段来跟踪它访问的上一个节点,当您完成搜索时,您可以按照 prev 链接跟踪您的路径。
代码是:
private static Queue<QNode> qNodes;
private static QNode endNode;
public static void main(String[] args) {
char[][] M = new char[][] { "0001110011".toCharArray(), "1111011110".toCharArray(),
"0110001010".toCharArray(), "S010101011".toCharArray(), "1110111E01".toCharArray() };
int r = findShortestPathBFS(M, 3, 0);
while ( endNode.prev != null && M[endNode.prev.x][endNode.prev.y] != 'S') {
M[endNode.prev.x][endNode.prev.y] = '*';
endNode = endNode.prev;
}
for ( char[] arr : M )
System.out.println(Arrays.toString(arr));
}
private static int findShortestPathBFS(char arr[][], int startX, int startY) {
if (arr[startX][startY] == 'E')
return 0;
int moveX[] = new int[] { 0, 0, 1, -1 };
int moveY[] = new int[] { 1, -1, 0, 0 };
boolean visited[][] = new boolean[arr.length][arr[0].length];
qNodes = new LinkedList<>();
qNodes.add(new QNode(startX, startY, 0, null));
while (!qNodes.isEmpty()) {
QNode currNode = qNodes.remove();
int currX = currNode.x;
int currY = currNode.y;
int currDistance = currNode.distance;
visited[currX][currY] = true;
// System.out.println(arr[currX][currY]);
if (arr[currX][currY] == 'E') {
endNode = currNode;
return currDistance;
}
for (int i = 0; i < moveX.length; i++) {
int newX = currX + moveX[i];
int newY = currY + moveY[i];
if (newX >= 0 && newX < arr.length && newY >= 0 && newY < arr[0].length && !visited[newX][newY]
&& arr[newX][newY] != '0') {
qNodes.add(new QNode(newX, newY, currDistance + 1, currNode));
}
}
}
return -1;
}
private static class QNode {
int x;
int y;
int distance;
QNode prev;
QNode(int x, int y, int distance, QNode prev) {
this.x = x;
this.y = y;
this.distance = distance;
this.prev = prev;
}
}
看到我将队列移到外面并使用了一个名为 endNode 的节点来跟踪井端节点,然后在搜索该 endNode 是否不为空(即如果找到)后,继续使用其上一个链接直到它为空。从语句中可以看出,起始节点将为空:qNodes.add(new QNode(startX, startY, 0, null));
输出是:
[0, 0, 0, *, *, *, 0, 0, 1, 1]
[1, 1, *, *, 0, *, *, 1, 1, 0]
[0, 1, *, 0, 0, 0, *, 0, 1, 0]
[S, 0, *, 0, 1, 0, *, 0, 1, 1]
[*, *, *, 0, 1, 1, *, E, 0, 1]