algorithm - 检索和存储路线图数据

Question

我正在开展一个项目，该项目的要求是检索特定源和目的地的地图相关数据。在未来的每个请求中，都将使用已获取的缓存信息。但是现在，如果源或目标发生变化，则将重建地图，其中包括旧的源和目标。

我的一些问题是：

1. 使用哪种数据结构，以便轻松搜索并轻松高效地找到源和目标之间的所有中间节点。

2. 我的内存资源有限，因此不可能在内存中拥有非常大的 DSC。

我正在考虑将源和目的地之间的路线数据存储为列表，但这可能会使搜索成为线性搜索，我希望不惜一切代价避免这种情况。如果在构建存储路径信息的结构时有一些开销是可以的，但搜索必须快速简单。我使用 java 作为编程语言。

预先感谢您的任何帮助

Answer 1

您应该将地图表示为图表。每个位置都将列出所有可以到达的下一个位置。这样，当您获得源和目标时，您可以执行 DFS 或 BFS 来确定将您从源带到目标的所有路径和所有中间节点。

由于您缓存了给定源和目标之间的路由，因此下次为不同的源或目标构建数据时，您可以尝试使用缓存的数据。