0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Dijkstra%27s_algorithm $\endgroup$
    – Steve Huntsman
    Oct 17, 2012 at 12:23
  • $\begingroup$ 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 $\endgroup$
    – Stuart
    Oct 17, 2012 at 12:54

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Stuart
    Oct 17, 2012 at 14:14
  • $\begingroup$ 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. $\endgroup$
    – Thomas Kalinowski
    Oct 17, 2012 at 14:42
  • $\begingroup$ 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' $\endgroup$
    – Stuart
    Oct 17, 2012 at 16:05
  • $\begingroup$ 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. $\endgroup$
    – Thomas Kalinowski
    Oct 17, 2012 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.