I have a directed graph with edges connecting nodes representing costs.


I wish to find the set of paths which 
-go from node 'start' to node 'end'
-are node-disjoint (except for the start and end node) (i.e. each node is used once)
-use all nodes in the graph
-minimises the total cost (or close enough\*)
-all costs are positive


In the example below, the red+green paths have the lowest cost, whilst using all nodes. The edges in blue are not used.


see <http://www.freeimagehosting.net/1lrts>


Is there an existing algorithm to efficiently solve this problem?


\*I am aware that it is likely NP in the worst case (e.g. start-node = end-node, fully connected graph is equivalent to the Travelling salesman problem). I need an algorithm which is fast and gives good results (possibly not optimal), rather than a simple optimisation trying every combination of possibilities, which is not computationally feasible in my case.



Finding the lowest cost set of disjoint paths using all nodes in a directed graph?
I don't see the equivalence to the travelling salesman problem. I think the following works for acyclic networks:


Split every node $v$ except start and end node into two copies $v^-$ and $v^+$, and add the arcs $(v^-,v^+)$. An arc $(v,w)$ of the original network is replaced by the arc $(v^+,w^-)$ with cost equal to the cost of $(v,w)$. Then your problem should be equivalent to finding a min cost flow with upper and lower capacity equal to one for the arcs of the form $(v^-,v^+)$. 


