BFS在网格中找到所有最短路径？

Question

我正在尝试实施BFS，以在网格中找到所有最短的路径。请注意，这不是一个，不是两个，而是全部。 让我们以9个节点的图表。连接是无方向性的，节点放置在网格状格式的节点中，如下：
0 1 2
3 4 5
6 7 8

每个数字表示一个节点的位置，并且所有节点之间都有链接，上面，下方，左下方或彼此右侧的所有节点之间都有链接。 这意味着0连接到1和3，而4连接到1、3、5和7等。

我试图从0到8的所有最短路径，这意味着总共6条路径。当我实施传统的BFS算法时，我注意到我缺少一些途径，因为代码将节点放入一组可见节点的方式。

例如，从0开始访问1和3之后，代码转移到0-1-2和0-1-4，之后仅查看0-3-6，而不是0-3-4，因为4通过节点1解析。

是否有办法通过BFS解决此问题？还是我应该使用其他搜索算法？先感谢您。