Fastest way to find n closest nodes to a given node in a directed weighted graph

Question

Right now I'm performing Dijkstra's algorithm on the entire graph and forming a min-heap of the nodes by total distance from the origin node. I then remove the top n elements from the heap.

This strikes me as seriously inefficient. Suppose I need to find the 10 closest nodes and my graph has over over 100000 nodes. Then performing Dijkstra's on the entire graph seems like a waste of time. But the problem is I'm not sure of any other way I can find the top 10 closest nodes without calculating the shortest path to each and every node in the graph.

Is there a better way?

Answer 1

Dijkstra works by iteratively adding the node which has the smallest distance to the source. This is the node whose distance we are sure of, there can never be a shorter path. So if we want to find the 10 closest nodes, we can simply terminate the search after we have added 10 nodes to our closed set.