使用邻接矩阵在迷宫图中找到最短路径-Java 学习之路

我在解决一个特定问题时遇到了一些麻烦，即在迷宫图中找到最短路径 . 可能是因为迷宫是由像_2458686这样的四维数组初始化的事实而陷入困境 . 第一对和第二对索引在行/列形成中指定图中的位置 . 该图如下所示：

XXXXXXXXXXXXX
..........X.X
X.XXX.XXX.X.X
X.X.X...X.X.X
X.X.XXX.XXX.X
X...X.....X..
XXXXXXXXXXXXX

ArrayList必须按从头到尾的顺序保存路径中顶点的位置 .

我已经编写了构造函数和连接方法;但是，我找到了最短路径方法的问题 . 以下是我如何创建迷宫图的示例：

final int edges[][] = {{1, 0, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1}, 
                {1, 2, 1, 3}, {1, 3, 1, 4}, {1, 4, 1, 5}, {1, 5, 1, 6}, 
                {1, 5, 2, 5}, {1, 6, 1, 7}, {1, 7, 1, 8}, {1, 8, 1, 9}, 
                {1, 9, 2, 9}, {1, 11, 2, 11}, {2, 1, 3, 1}, {2, 5, 3, 5}, 
                {2, 9, 3, 9}, {2, 11, 3, 11}, {3, 1, 4, 1}, {3, 3, 4, 3}, 
                {3, 5, 3, 6}, {3, 6, 3, 7}, {3, 7, 4, 7}, {3, 11, 4, 11}, 
                {4, 1, 5, 1}, {4, 3, 5, 3}, {4, 7, 5, 7}, {4, 11, 5, 11}, 
                {5, 1, 5, 2}, {5, 2, 5, 3}, {5, 5, 5, 6}, {5, 6, 5, 7}, 
                {5, 7, 5, 8}, {5, 8, 5, 9}, {5, 11, 5, 12}};

        MazeGraph maze = new MazeGraph(13, 7); 

        for (int[] edge : edges) 
            maze.connect(new Location(edge[0], edge[1]), new Location(edge[2], edge[3]));

1 回答

0
首先，这个
```
adjacent = new boolean[height][width][height][width];
```
与此相矛盾：

第一对和第二对索引在行/列形成中指定图中的位置 .

它是列/行，而不是行/列 .

Dijkstra's algorithm应该为你的矩阵实现 . 引用：

让我们开始的节点称为初始节点 . 设节点Y的距离是从初始节点到Y的距离.Dijkstra算法将分配一些初始距离值，并尝试逐步改进它们 . 为每个节点分配一个暂定距离值：为我们的初始节点设置为零，为所有其他节点设置为无穷大 . 将初始节点设置为当前节点 . 标记未访问的所有其他节点 . 创建一组称为未访问集的未访问节点 . 对于当前节点，考虑其所有未访问的邻居并计算其暂定距离 . 将新计算的暂定距离与当前指定的值进行比较，并指定较小的临时距离 . 例如，如果当前节点A被标记为距离为6，并且将其与邻居B连接的边缘具有长度2，那么到B（通过A）的距离将是6 2 = 8.如果B先前被标记如果距离大于8，则将其更改为8.否则，保持当前值 . 当我们考虑当前节点的所有邻居时，将当前节点标记为已访问并将其从未访问的集合中删除 . 永远不会再次检查受访节点 . 如果目标节点已被标记为已访问（当计划两个特定节点之间的路由时）或未访问集中的节点之间的最小暂定距离是无穷大（当计划完整遍历时;在初始节点之间没有连接时发生）和剩下的未访问的节点），然后停止 . 算法已经完成 . 否则，选择标记有最小暂定距离的未访问节点，将其设置为新的“当前节点”，然后返回步骤3 .
回复于 2024-04-20T09:27:34+08:00

使用邻接矩阵在迷宫图中找到最短路径

1 回答

相关问题