如何从最短路径算法中提取路径

本文关键字：提取 路径 算法 最短路径 | 更新日期: 2023-09-27 18:04:50

我试图实现一个"6度"风格的算法，因为我试图找到两个链接之间的最短路径。在这个场景中，它是一个电子游戏，它有区域地图，这些地图有相互连接的传送门/翘曲。

每个地图都有一个地图ID int id，并且可以有几个门户，实现为List<Portal>。
每个传送门将指向的地图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点的步骤顺序。

我完全不知道从哪里开始，虽然。我如何解开路径?

如何从最短路径算法中提取路径

当你做newQueue.Add(tm);时，你也应该记录你来自哪里。一个简单的解决方案是将关系添加到字典:dict.Add(tm,p)。最后，只需请求当前门户的父门户，就可以使用该字典从目标返回路径。

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

起始点的代价为0。所有其他区域的代价都是无穷大

维护一个可达区域队列。一开始只有起始区

迭代可达区域，始终选择成本最低的区域。

对于每个直连区域，计算(成本+当前区域)+(获取连接翘曲点的成本)。

如果该值小于邻居区域的当前开销值，则更新开销值，设置指向当前区域的反向链接指针，并将其加入队列。

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

然后，从目的区域，按照反向链接指针形成你的路径。

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

相关文章：