Given a node $x$ on a weighted graph, what algorithms are there for finding which node has the shortest path to $x$ from a given list of nodes?

Question

Question: We are given this problem: On a weighted graph, a node $x$ and a set of nodes $L$, which of the nodes in $L$ has the shortest path to $x$?

I would like to know if this problem has a faster solution than just calculating the distance from each node to $x$ using some solution to the shortest path problem, and choosing the node with the lowest number. Furthermore, I'm wondering if this particular problem has some name and if there are known algorithms for solving the problem that has been described in the literature.

Answer 1

Like you said, we could just use Dijkstra's algorithm (usually) to calculate the distance from our initial node $x$ to each node $l_i \in L$. However, this would take a while, as you may imagine.

So, what we can do is create a new node $v$, and connect it only to each $l_i \in L$. Then, we apply Dijkstra's algorithm to find the shortest $x$-$v$ path. Now we just look at the node that comes before $v$ in that path, and that would be the node in $L$ that's closest to $x$.

This problem is similar to optimizing network flow with multiple sources and sinks. The technique for that is to create a supersink, or supersource. It's exactly what we did here, except with paths.

Answer 2

I had an idea that might help. Collapse the nodes in $L$ into one single node $L'$ and make the weight of node $L'v$ the weight of the lightest edge between a vertex of $L$ and $v$. Now you only need to calculate the distance between $L'$ and $x$

Answer 3

Applying Dijkstra's algorithm to this case is very straightforward. If you choose $x$ as the starting node, and use a min-heap to go through the nodes in order of distance from $x$, then the first node you reach that is $\in L$ is the closest node to $x$ that is $\in L$.

create a min-heap and insert x with distance 0
create an empty set of visited nodes
while the heap is not empty:
  remove the node with the minimum distance from the heap (call it n)
  if n is not in the visited set:
     add it to the visited set
     for each node m connected to n:
       if m is in L:
         m is the closest node to x
         return m and terminate algorithm
       if m is not in L:
         add m to the heap with distance: n's distance + distance from n to m
if the heap becomes empty before the inner for loop returns:
  no nodes in L are reachable from x