# Finding the lowest cost set of disjoint paths using all nodes in a directed graph?

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.

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.

• en.wikipedia.org/wiki/Dijkstra%27s_algorithm Oct 17, 2012 at 12:23
• Unfortunately Dijkstra's algorithm finds only a single path from start to end, of minimal cost. However, I want multiple disjoint paths (using each node exactly once). -Stuart Oct 17, 2012 at 12:54

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