0
$\begingroup$

After asking another question(Is the last step in the Christofides' algorithm necessary), I have decided Christofide's algorithm probably doesn't solve the problem I'm facing.

Is there any algorithms that would best suit this problem?

The input is a set of nodes on a graph (an implementation would be similar to the illustration in the question), and the required output is the shortest path that visits every specified node before finally reaching the specified end node.

$\endgroup$
8
  • 2
    $\begingroup$ is the node sequence in order? if not then you are in traveling salesman territory (NP complete) $\endgroup$ – ratchet freak Jan 7 at 16:22
  • $\begingroup$ Can you link to or credit the source of all copied material? $\endgroup$ – D.W. Jan 7 at 17:49
  • $\begingroup$ It's my material so no need @D.W. $\endgroup$ – Adam Cole Jan 7 at 20:00
  • $\begingroup$ @ratchetfreak the node sequence is whatever makes the path from a starting node to an end node the shortest $\endgroup$ – Adam Cole Jan 7 at 20:01
  • 1
    $\begingroup$ Rather than responding with comments, please edit the question so it has all the information needed and so it reads well for someone who encounters the question for the first time. Then, flag the comments as no longer needed. We want people to be able to understand what is being asked without having to read the comments. Thank you! $\endgroup$ – D.W. Jan 7 at 23:18

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.