ask*_*ask 4 graph dijkstra shortest-path min-heap closest-points
现在我正在整个图上执行Dijkstra算法,并通过距离原点节点的总距离形成节点的最小堆.然后我从堆中删除前n个元素.
这让我感到非常低效.假设我需要找到10个最近的节点,我的图表有超过100000个节点.然后在整个图表上执行Dijkstra似乎是浪费时间.但问题是我不确定我能找到前10个最近的节点而不计算图中每个节点的最短路径.
有没有更好的办法？
Dijkstra通过迭代添加距离源最小的节点来工作.这是我们确定距离的节点,永远不会有更短的路径.因此,如果我们想要找到10个最接近的节点,我们可以在将10个节点添加到闭合集后简单地终止搜索.