0
$\begingroup$

Let us consider a Directed Acyclic Graph $G(V,E)$ such that all edges have unit weight. Let $s$ be a source node, $s\in V$ and a set of destination nodes, $D\in V\backslash s$. My problem is to find a node $d\in D$ such that $d$ has a path of unique length $l>0$ from source node, $s$ to destination node, $d$ (i.e no other node in $D$ has a path of length $l$ from the source node $s$). There could be multiple destination nodes $d_1,d_2,...$ such that $d_1$ has a path of unique length $l_1$ and $d_2$ has a path of unique length $l_2$ from the source node and so on. How to find such nodes? Is there any algorithm or modification to existing algorithm to solve the problem?

$\endgroup$
6
  • $\begingroup$ You can take $l = 0$ and $d = s$. $\endgroup$ – Yuval Filmus Jun 4 at 10:52
  • $\begingroup$ I need to find $d$ such that there is a path of unique length $l>0$ from $s$ to $d$. Thank you. $\endgroup$ – user49739 Jun 4 at 16:44
  • $\begingroup$ Please edit your question to revise it based on feedback. Don't leave clarifications in the comments -- we don't want people to have to read the comments to understand what you are asking. Instead, revise your question to read well for someone who encounters it for the first time. $\endgroup$ – D.W. Jun 4 at 22:53
  • $\begingroup$ Try using dynamic programming: cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Jun 4 at 23:35
  • $\begingroup$ You can take $l = 1$ and any out-neighbor of $s$. $\endgroup$ – Yuval Filmus Jun 5 at 5:11

Your Answer

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

Browse other questions tagged or ask your own question.