1
$\begingroup$

I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node. This seems like a common problem to need to solve, but I haven't found much material on it. Does anyone know if this particular problem has a name, or any published material (formal or informal) related to it?

Note, I am not asking for a solution to the problem itself. I am interested in finding material related to the problem. For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first. I believe a modified version of the Uniform Cost Search will do what I want, since it does not enqueue all the nodes first. Things get more interesting in this case, because you don't have full knowledge of all shortest paths. I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process. I think this is possible using an admissible heuristic as in the A* search. These are the kinds of details I want to be able to read up on.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

Question 1. For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.

Yes, you are right about the disadvantage of canonical Dijkstra's algorithm. However, it can be easily adapted (wiki):

The algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).

See the paper for details (including experiments) on implementing Dijkstra's algorithm with such a modified priority queue.

Question 2. I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.

The Dijkstra's algorithm finds the shorted paths from a starting node in the order of increasing costs. So, the first $n$ vertices removed (delete-min) from the priority queue are the $n$ closest nodes from a starting node you are looking for.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Modifying Dijkstra's algorithm in the way you describe is called Uniform Cost Search, which I already mentioned in the question. I know that Dijkstra's algorithm is guaranteed to find a set of shortest paths to each node, and I know that Uniform Cost Search is guaranteed to find a set of shortest paths to each node if you let it run to completion. I was not sure if this guarantee holds if you interrupt the algorithm early, but after thinking about it just a little more I realized that it has to be b/c paths pulled off the priority queue are never altered later in the algorithm. $\endgroup$
    – Tony
    Jun 16, 2015 at 19:32
  • $\begingroup$ Thanks for the reference to the original paper on Uniform Cost Search. I'm still curious if there's any research relating to selecting the nodes closest to a node instead of finding shortest paths to all nodes, which is what the question is asking about. $\endgroup$
    – Tony
    Jun 16, 2015 at 19:34
  • $\begingroup$ @Tony I don't get it. You don't have to find the shortest paths to all nodes. You can terminate the Dijkstra's algorithm once it finds the first $k$ closest nodes. $\endgroup$
    – hengxin
    Jun 17, 2015 at 1:41
  • $\begingroup$ I've never said that I want to find the closest path to all nodes. $\endgroup$
    – Tony
    Jun 17, 2015 at 17:09
  • 1
    $\begingroup$ @Tony Yes, you have the guarantee as long as all edge weights are positive and the whole graph are known (not processed) in advance. This is an important property of Dijkstra's algorithm. $\endgroup$
    – hengxin
    Jun 18, 2015 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.