如何在对象数组中找到两个节点之间的最短路径？

Question

我有10,000多个数据（Users）来自一个JSON格式的API并给出两个节点（即2个Users），我想找到两个Users之间的最短路径。

当我意识到找到最短的路径时，我可以使用Dijkstra的算法，但是为了做到这一点，我必须创建一个不足10,000+数据的图形。

例如，我发出了API请求

fetch('https://jsonplaceholder.typicode.com/users')
  .then(res => res.json())
)

每个用户都是一个对象

  {
    "name": "Leanne Graham",
    "address": {...}
    },
    "website": "hildegard.org",
    "company": [
      "Romaguera-Crona",
      "Google",
      "Facebook"
    ]
  }

问题是要了解两个用户如何根据他们所服务的公司相互关联

我根本无法开始，因为数据是如此巨大。我想知道，我们怎么能这样做呢？我们创建一个图并应用Dijkstra的算法吗？

我所做的就是真正遍历每个用户并检查公司数组。

Users.filter(user => user.companies.include([...]))

Answer 1

据我所知，这是你在How to create edges between nodes that have similarities中减少问题的原始问题。您的减少是有用的，但是如果不知道数据的性质，即代表一个人工作的公司，问题就会变得更加普遍。因为这是真实数据，我们可以假设一些事情，比如用户平均没有超过10个工作条目，并且并非所有用户都在同一家公司工作。这意味着图表将相当稀疏。

要构建用户图表，您可以从另一篇文章中继续我的第二个建议：

• 构建从公司名称到为该公司工作的所有用户的集合的映射
• 迭代公司名称，遍历为每个公司工作的所有用户对，如果他们尚未连接，则将它们连接到边缘

这仍然是一个相当大的图表：对于10k用户，如果用户平均与其他100个用户合作，则可能会产生一百万个边缘。然而，现代计算机无法存储在RAM中。我不确定Javascript的内存效率如何 - 如果您愿意切换到更高性能的语言，您可以考虑使用该选项。

现在你有一个图表，想要找到两个节点之间的最短路径（重复，我假设）。请注意，由于您的图形没有权重，因此不需要Djikstra的算法。你可以运行一个在O(N+M)时间工作的BFS，其中N是用户数，M是边数。对于一百万个边缘，它可以在Java中舒适地运行一秒钟，但在Javascript中可能需要几个。