波波老师，我想打印所有的最短路径，但结果只能输出一条，您能看看是哪里出问题了吗，我定义了一个结构体，记录坐标和当前的路径，队列存储结构体类型。

Question

我定义了一个结构体，记录坐标和当前的路径，队列存储结构体类型。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class GoMaze {
//走迷宫问题
//经典的bfs模板记录路径题
//(0, 0)->(1,0)->(2,0)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)
static class Node{
int x;
int y;
String sb;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
//设置方向数组
static int [][] dir={{-1,0},{0,1},{1,0},{0,-1}};
//设置标记数组避免走回头路
static boolean [][] visited;
//最短路径集合
static ArrayList res=new ArrayList();

public static void main(String[] args) {
    //初始化迷宫图案(Initializes the maze pattern)
    int [][] maze = {
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 1},
        {0, 1, 1, 0, 0},
        {0, 1, 0, 1, 0}
    };
    bfs(maze);
    //这个版本只能记录一条最短路径(思考：假如要记录所有的最短路径该如何修改)
    System.out.println(res);
}
public static void bfs(int [][] maze){
    int m=maze.length,n=maze[0].length;
    visited=new boolean[m][n];
    Deque<Node> q=new ArrayDeque<Node>();
    Node p=new Node(0,0);
    p.sb="("+p.x+","+p.y+")";
    q.add(p);
    visited[p.x][p.y]=true;
    //标准的bfs框架相当于N叉树的遍历
    while (!q.isEmpty()){
        Node cur=q.poll();
        if(cur.x==m-1&&cur.y==n-1){
            res.add(cur.sb);
        }
        for(int i=0;i<4;i++){
            int nx= cur.x+dir[i][0];
            int ny= cur.y+dir[i][1];
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&!visited[nx][ny]&&maze[nx][ny]==0){
                Node nextp=new Node(nx,ny);
                nextp.sb=cur.sb+"->("+nextp.x+","+nextp.y+")";
                q.add(nextp);
                visited[nx][ny]=true;
            }
        }
    }
}

}

Answer 1

liuyubobobo 2020-12-25 19:57:49

如果要找所有的最短路径，不能用 visited。

visited 保证了一个点访问了一次以后，就不会再访问了。但是一个点有可能有多条相同的最短路径访问的方式。

你可以使用这样一个简单的图，来跟踪一下你的代码，看看 visited 是如何起作用的，你的代码只找到了从 0 到 3 的一条路径，而不是两条。第二条为什么没有被记录？

  0
 / \
1   2
 \ /
  3

但是，求所有路径，由于解是指数级的，所以通常不会要求这么做。

你可以考虑上面的图，如果我再加三个顶点，从 0 到 6 的最短路有 4 条。

  0
 / \
1   2
 \ /
  3 
 / \
4   5
 \ /
  6

如果我再加三个顶点，从 0 到 9 的最短路有 8 条。

  0
 / \
1   2
 \ /
  3 
 / \
4   5
 \ /
  6
 / \
7   8
 \ /
  9

按照这个方式，每多加 3 个顶点，最短路的个数就要乘以 2。

我要是再加 999 个点，最短路有多少条？

这是指数的：）

继续加油！：）

• 提问者 weixin_慕沐2087304 #1

  那老师力扣126题就是输出所有最短的序列，该使用什么去操作呢，我看您的题解有点不太明白。您可以说下思路吗

• liuyubobobo 回复 提问者 weixin_慕沐2087304 #2

  这里的代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0126-Word-Ladder-II/cpp-0126/main.cpp 首先来说，标记出到每个节点的最短路径距离（bfs 做的事情）。之后的关键是，getRes 使用回溯的方式，求解出所有路径。比如这个回答我举的例子中，到达 9 的最短路径长度是 6，到达 7 和 8 的最短路径长度是 5 且都能到达 9，所以 7->9 和 8->9 都是结果，继续回溯去看如何能到达 7 和 8，依次类推。

• 提问者 weixin_慕沐2087304 回复 liuyubobobo #3

  谢谢波波老师，懂了