如何提取该最短路径算法所采用的路径？

Question

我正在尝试实现“6 度”式算法，因为我正在尝试找到两个链接之间的最短路径。在这种情况下，它是一款视频游戏，具有区域地图，其中具有相互链接的门户/扭曲。

每个地图都有一个地图 ID，int id，并且可以有多个门户，实现为 List。
每个门户都通向一个地图，int ToMapID 并具有包含它的地图，Map HomeMap。

不管怎样，我已经成功地找到了两张地图之间最少的扭曲数，这很好，因为这就是我想要的。问题是，我很难理解如何记录从 A 点到 B 点的路径。

这是我已经实现的：

Map start = allMaps[0];
Map end = allMaps[1];

int distance = 0;

List<Portal> alreadyChecked = new List<Portal>();
List<Portal> queue = start.Portals;

while (queue.Count > 0) {
    distance++;
    List<Portal> newQueue = new List<Portal>();
    foreach (Portal p in queue) {
        foreach (Portal tm in theMap.Portals) {
            if (!alreadyChecked.Contains(tm)) {
                alreadyChecked.Add(tm);
                if (tm.ToMap == end.ID) {
                    Console.WriteLine("Found a path, it is " + distance + " map(s) away;");

                    Console.ReadKey();
                    Environment.Exit(0);
                }
                newQueue.Add(tm);
            }
        }

    }
    queue = newQueue;
}

理想情况下，我想要一个 Map[ 数组]，其中包含从 A 点到 B 点的步骤顺序。

不过，我完全不知道从哪里开始。我如何解开道路？

Answer 1

当您执行 newQueue.Add(tm); 时，您还应该记录您来自哪里。一个简单的解决方案是将关系添加到字典：dict.Add(tm,p)。最后，您可以使用此字典通过简单地询问当前门户的父级来从目标向后走路径。

Answer 2

最短路径的工作原理基本上是这样的：

起点以零成本开始。所有其他区域都以无穷大的成本开始。

维护可达区域的队列。最初只有起始区域。

遍历可达区域，始终选择成本最低的区域。

对于每个直接连接的区域，计算（成本+当前区域）+（获取连接扭曲点的成本）。如果该值小于相邻区域的当前成本，则更新成本，设置指向当前区域的反向链接指针，并将其添加到队列中。

重复此操作，直到下一个要处理的区域（队列中成本最低的区域）的成本等于或大于目标区域。

然后，从目标区域沿着反向链接指针形成您的路径。

在所有链接具有相同成本的简单情况下，您可以只使用 FIFO 队列，它将保持排序。如果旅行费用有所不同，您将必须按区域费用对队列进行排序。