在一个有向加权图中，找到离给定节点最近的n个节点的最快方法。

Question

4

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

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

有更好的方法吗？

- ask

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JSQuareD · Accepted Answer

Dijkstra算法通过反复添加到源点距离最小的节点来工作。这是我们确定距离最短的节点，不存在更短的路径。因此，如果我们想找到最接近的10个节点，只需在将10个节点添加到封闭集之后终止搜索即可。