Algorithm to find a 'minimal spanning path'?

Question

Inspired by this comic http://xkcd.com/173/

I know that there are many algorithms to find the minimal spanning tree of a weighted graph, however I've been struggling to find any which can find the minimal spanning 'path'.

For the comic, if we weighted every edge based on each pairs relationship, then the socially optimal arrangement would be the minimal spanning 'path', i.e. a path which spans all the vertices. Can anyone help?

Answer 1

Finding an optimal Hamiltonian path (also known as an optimal path cover) is a difficult problem. (Determining whether any Hamiltonian path exists is an NP-complete problem.) This scholarly article discusses, among other things, an optimal path cover algorithm. You can search the web for these terms to find other resources. I don't know of any readily available code.

Incidentally, this question (which is basically a duplicate of yours) clearly explains why the Travelling Salesman Problem not the place to start.