如何在随机生成的迷宫中找到最远的两个点？

Question

注意：我已经有一种随机生成迷宫的方法，在这里找到：

https://en.wikipedia.org/wiki/Loop-erased_random_walk

我正在寻找一种算法，以在完成的随机生成的迷宫中找到两个最远的单元。我的意思不是最远，因为如果要从一个单元格到另一单元格绘制一条直线，则该线的长度最长。这总是会导致以下两种情况之一：

1. 选择左上角单元格和右下角单元格。

2. 选择了右上角的单元格和左下角的单元格。

我打算找到一种算法来查找两个单元格，如果您一次要从一个单元格到第二个单元格被一个相邻的单元格（上，下，左或右）旅行，而不经过迷宫的墙壁，这将需要您穿过最多的细胞。

Example of Randomly Generated Maze Using the Algorithm Found in the Link Above

谢谢你。

Answer 1

有一种称为Dijkstra's algorithm的算法，最初被设计为查找两点之间的最短路径。这听起来似乎与您要寻找的相反，但是如果您学习算法，则可以使用条件来获得相反的结果：找到最长的路线。

这里是解释该算法的Wiki：https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

以下是解释该算法的视频：https://www.youtube.com/watch?reload=9&v=pVfj6mxhdMw

Answer 2

如@Luis所指出，您绝对应该签出Dijkstra's algorithm。但是，您需要添加许多其他约束。不重新访问单元（否则，对于3格迷宫本身，您可以拥有最长的路径作为无限路径）。