0

以下是我存储在哈希图中的数据集，我必须找到两个值之间的最短路径。

9244, 4322, 4886, 5989, 8598, 9979, 1447, 9657
8598, 6752, 7146, 1951, 660, 1447, 7779
568, 1951, 4886, 2570, 9026, 9489, 7779
6752, 3424, 1977, 4746, 9657
77

哈希映射的键值是每行的第一个值，其余的是 9244 的假定“朋友”（在每种情况下都相同）。

我以这种格式保存在哈希表中：hashmap(key, array)，其中：

  • 密钥是例如 9244
  • 然后数组保存 [ 4322, 4886, 5989, 8598, 9979, 1447, 9657 ]

如何找到两个键之间的最短路径？

4

2 回答 2

1

如果我正确解释了您的问题，那么您说的是有向图的最短路径问题。

  • 从整数开始，获取它映射到的整数数组。
  • 这些整数中的每一个都是新数组的关键。
  • 按照这些路径并找到最短的路径。

如果您进行 google 搜索，并查看 Wikipedia 页面，您将能够找到大量对您有帮助的代码示例和算法。

正如 Peter Smit 所提到的，A*算法是解决这个问题的常见算法。其他包括Dijkstra's和Bellman-Ford。

于 2009-04-23T07:21:06.310 回答
0

您可以实现A*算法。您可以先从中构建一个图表，然后按照维基百科页面上的伪代码进行操作。

于 2009-04-23T07:19:37.280 回答