Find the shortest path in a graph which visits certain nodes.

Posted by dmd on Stack Overflow See other posts from Stack Overflow or by dmd
Published on 2008-10-21T16:01:56Z Indexed on 2010/05/10 20:14 UTC
Read the original article Hit count: 272

I have a undirected graph with about 100 nodes and about 200 edges. One node is labelled 'start', one is 'end', and there's about a dozen labelled 'mustpass'.

I need to find the shortest path through this graph that starts at 'start', ends at 'end', and passes through all of the 'mustpass' nodes (in any order).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt is the graph in question - it represents a corn maze in Lancaster, PA)

© Stack Overflow or respective owner

Related posts about graphs

Related posts about algorithm