graph - 在有向加权图中找到与给定节点最近的 n 个节点的最快方法

Question

现在我正在对整个图执行 Dijkstra 算法，并通过与原始节点的总距离形成节点的最小堆。然后我从堆中删除前 n 个元素。

这让我觉得效率非常低。假设我需要找到 10 个最近的节点，而我的图有超过 100000 个节点。然后在整个图表上执行 Dijkstra 似乎是在浪费时间。但问题是我不确定是否有任何其他方法可以在不计算图中每个节点的最短路径的情况下找到前 10 个最近的节点。

有没有更好的办法？

Answer 1

Dijkstra 通过迭代添加与源距离最小的节点来工作。这是我们确定距离的节点，永远不可能有更短的路径。因此，如果我们想找到最近的 10 个节点，我们可以在将 10 个节点添加到封闭集中后简单地终止搜索。