java - 未加权二维数组中的最短路径。如何显示 BFS 期间采取的步骤/方向

Question

我在这个算法中试图做的是，给定一个二维数组，找到从给定起点 (S) 和给定终点 (D) 的最短路径——记住数组中的一些元素 (*)被视为障碍。通常，我会执行典型的 BFS 并返回最短路径的距离，但会有一些额外的问题。我需要显示通过用路径到达目的地的基本方向（北、南、东或西。分别缩写为 n、s、e、w）替换遍历元素所采取的最短路径。在多条最短路径的情况下，您可以向南或向东到达目标，该元素将填充基本方向的组合，即“se”，如第二张图片所示。请注意，这并不意味着东南，因为不允许对角线遍历。我熟悉在算法中使用 BFS，但是对于如何标记包含的方向所采用的路径，我有点困惑。我不一定要寻找一个成熟的算法来回答这个问题，而更多的是一个伪代码的答案，让我走上正轨。第一张图片是样本输入数组，第二张图片是所述输入数组的“解决方案”。TL：DR 我正在寻求有关如何在执行 BFS 时跟踪通过网格的方向的建议，非常感谢任何和所有帮助/反馈，并提前感谢您！

标签： javamultidimensional-arraybreadth-first-searchshortest-path

Answer 1

您可以用一条元数据标记每个节点（数组条目）：最短路径长度。这可以通过各种算法来完成，但 BFS 基本上可以让你到达那里。每个可到达的节点都应该有一个数字。

从您的示例中，S 将是零（从 S 到 S 的零步数），而 D 是 16（从 S 到 D 的 16 步）。现在您拥有所需的一切。

你现在可以：

1：选择结束节点（d=16）

2：搜索其附近（n，e，s，w）

3：如果节点有 d-1，写（附加）一个字母，具体取决于您正在查看其附近的四个方向中的哪一个。忽略其他节点。

4：选择所有具有 d-1且至少有 1 个字母的节点

5：Foreach 选择的节点，执行步骤 2 - 3

6: if(d-1 > 0) d = d-1 并执行步骤 4 - 5

这是可以做到的算法的粗略形状。它适用于任何位置的 D。但是，如果您移动 S，则需要重新标记每个节点。