I have an undirected graph where each vertex is given some items from a set of items. My goal is to find the lowest cost path from my source vertex to destination vertex while collecting all such items.

The added constraint is that I may split my path once at a node once to collect items from some other path and reach my destination some other way and the total cost would be the minimum of the two paths.

I have been stuck at this for days now and can't seem to figure out an algorithm to solve this..

  • 1
    $\begingroup$ Please edit the question to give one or more examples. The more detail, the better in general. $\endgroup$
    – John L.
    Commented May 17, 2020 at 11:49
  • $\begingroup$ Please edit the question to add a reference to the original source. Or explain the background about why you formulated this problem. $\endgroup$
    – John L.
    Commented May 17, 2020 at 18:01


Your Answer

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

Browse other questions tagged or ask your own question.