在 2d 阵列中查找最短路径

Question

我需要找到从左上角到右下角的最短路径。规则是它必须从A到B到A到B等。例如，见图片：上图的预期输出为 13。我试图用一个dijkstra算法在java中实现这一点，但后来卡住了。这是正确的方法吗？

Answer 1

如果目标是找到从左上角到右下角（或任何任意2点之间）的最短路径，dijsktra是一种可能的方法，但是您必须从输入正确构造图形。

在这种情况下，我会选择一个简单的算法。您可以找到几个在线资源来解释它，包括此视频或本文，因此我不会在此答案中详细介绍。flood-fill

如果您正确实施了规则（仅 A 到 B 和 B 到 A），则可以仅使用 2 个矩阵（一个用于原始字母数组，一个用于距离）找到最短路径。

Answer 2

您可以使用任何图形遍历算法或任何寻路算法。T，这里有很多算法，如A *，Dijekstra，BFS，DFS ...

例如，让我们以BFS为例，它查找图形的2个节点之间的最短路径。假设您的 2d 数组是一个图形，如果 2 个节点之间的距离为 1 且其中一个节点为 A，第二个节点为 B https://en.wikipedia.org/wiki/Breadth-first_search，则边缘处于状态。)

只需从矩阵构造图形并为图形实现 BFS，或者您可以简单地为数组实现 BFS。