寻找2d阵列中的最短路径

Question

我需要找到从左上角到右下角的最短路径。

规则是必须从A到B到A到B等。

见图为例：

上面图片的预期输出是13。

我试图用java中的dijkstra算法实现这个，但后来卡住了。这是正确的方法吗？

Answer 1

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

在这种情况下，我会选择一个简单的flood-fill算法。你可以找到几个解释它的在线资源，包括this video或this article，所以我不会在这个答案中详细介绍。

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

Answer 2

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

例如，让我们采用BFS，它找到图形的2个节点之间的最短路径。假设，你的2d数组是一个图形，如果两个节点之间的距离为1且其中一个节点为A而第二个节点为B，则边缘处于条件状态。这里读取关于BFS的模式（https://en.wikipedia.org/wiki/Breadth-first_search）

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