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.

singlepath from start to end, of minimal cost. However, I wantmultipledisjoint paths (using each node exactly once). -Stuart $\endgroup$ – Stuart Oct 17 '12 at 12:54