1
$\begingroup$

If you have directed and unweighted graph G how could you find a path from node s to node t that also goes through another node w? This could be a non-simple path.

$\endgroup$
2
$\begingroup$

If you don't care about simplicity, a path from $s$ to $t$ that goes through $w$ is just a path from $s$ to $w$ concatenated with a path from $w$ to $t$.

$\endgroup$
  • $\begingroup$ Okay so what if instead of going through node w, every node is colored either red or blue and we need a path from s to t that goes through a red node. Would that be a similar solution? I do feel like that could get complicated very quickly if there are hundreds of red vertices and only one of them leads to t. $\endgroup$ – imdumb Apr 19 '18 at 16:00
  • $\begingroup$ It's not much harder to find a path from a vertex to a set than it is to find a path from a vertex to another vertex. $\endgroup$ – David Richerby Apr 19 '18 at 16:02

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.