# 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 – Steve Huntsman Oct 17 '12 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 – Stuart Oct 17 '12 at 12:54

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

• My thought was that, if the start and end were the same point, then it would be a problem equivalent to visiting all cities exactly once (nodes), finding the minimum cost path (i.e. the TSP but allowing multiple visits to the starting point, which of course would not be used anyway in the optimum case). You suggestion to reformulate as a flow problem is interesting, and I will look into it. Thank you. – Stuart Oct 17 '12 at 14:14
• Why would the multiple visit option not be used in an optimal solution? If you have zero cost arcs in both directions between the start node and every other node and all other arcs have positive cost then the optimal solution is to always return to the start/end node after visiting any other node. – Thomas Kalinowski Oct 17 '12 at 14:42
• You are of course correct in your example, however in the usual formulation of the TSP, the graph is fully connected, and the cost of going direct from one city to another is lower than the cost of going somewhere else, and then direct to the city (or is the same), so there would be no point in revisiting a node (the cost will never be lower). I'm not sure it matters either way, the point is that the problem is equivalent, and is NP in the general case. Reading through the literature, it would appear that I can formulate the problem as a the 'minimum cost circulation problem' – Stuart Oct 17 '12 at 16:05
• I see. You mean the metric TSP. By the way, from the NP-hardness it follows immediately that in general the min cost circulation approach cannot work (you might get cycles not containing start and end node). But at least it should work for acyclic networks. – Thomas Kalinowski Oct 17 '12 at 16:59