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.
Best Answer
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^+)$.