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

Question

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

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

有没有更好的办法？

Answer 1

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