1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ how is this different to my solution? $\endgroup$ – Jorge Fernández Hidalgo Sep 28 '14 at 18:34
  • $\begingroup$ @JorgeFernández Adding a new vertex is less disruptive to a graph than collapsing an entire collection of vertices. One has to account for assigning new weights, rebuilding the collapsed portion so as to tell the user what vertex in $L$ was the closest one, and other hiccups. $\endgroup$ – Andrey Kaipov Sep 28 '14 at 20:01
  • $\begingroup$ I'm sorry, what is a user ? I don't see any difference between colapsing and adding, it is the same computation with the added or colapsed vertex. $\endgroup$ – Jorge Fernández Hidalgo Sep 28 '14 at 20:20
  • $\begingroup$ @Sid You wanted to know if this problem had a particular name. See my edit. Unfortunately I don't know of anything that talks about paths specifically, but the technique is similar. $\endgroup$ – Andrey Kaipov Sep 28 '14 at 20:26
  • $\begingroup$ @JorgeFernández The user is the person implementing the algorithm. It's who the output goes to. Collapsing introduces unnecessary steps into the problem (like undoing the contraction). It works, but graphs tend to be large, and when implemented into a computer, efficiency matters. $\endgroup$ – Andrey Kaipov Sep 28 '14 at 20:29
1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks for your reply. But how do you collapse the nodes into a single vertex? Also, have you previously heard about this algorithm or the problem somewhere in the literature? $\endgroup$ – Sid Sep 28 '14 at 16:24
  • $\begingroup$ delete the nodes in $L$ and add a node $L'$, the edge $L'v$ exists if there was an edge $lv$ with $l$ in $L$ int he original graph. make the weight of the edge $L'v$ the minimum weight of an edge of the form $lv$ with $l$ in $L$ $\endgroup$ – Jorge Fernández Hidalgo Sep 28 '14 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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