8
$\begingroup$

A car has to pick up each person and take them to their destination. I am trying to find the shortest tour that will do this. How can I find the shortest path between any s and t.... visiting all vertices, and without coming back to the start?

competition

In this case I have 10 points. After each For[], I obtain an array with the distances from i to j.

t = {
  {{2, 1}, {5, 2}},
  {{7, 1}, {9, 4}},
  {{9, 2}, {6, 6}},
  {{5, 4}, {2, 3}},
  {{4, 5}, {7, 9}},
  {{8, 5}, {2, 4}},
  {{3, 7}, {7, 7}},
  {{4, 8}, {1, 10}},
  {{3, 10}, {10, 7}},
  {{9, 10}, {9, 8}}
  }
(* t[[i,j,k]    i\[Rule]Trip Nºi    j\[Rule] \
1=Inicio=Pick-Up  2=Fin=Drop-Off     k\[Rule] 1ª o 2ª componente (es \
decir x ó y) *)

Array[t2t, {10, 10}]
For[i = 1, i <= 10, i++,
 For[j = 1, j <= 10, j++,
  If[i != j,
   t2t[i, j] = 
        Sqrt[(t[[j, 1, 1]] - t[[i, 2, 1]])^2 + 
        (t[[j, 1, 2]] - t[[i, 2, 2]])^2], t2t[i, j] = Infinity
   (* In t2t there is the distance from i to j 
      different from distance from j to i, in general *)
   ]
  ]
 ]

I want to find the shortest tour through the 10 vertices, with the weight/distsances t2t[i,j] visiting all vertices, and not coming back to the start.

-- After comments on March´2015 I add the original problem published in ORMS magazine -- Now this kind of puzzles are published in Amalytics ( for example electriying in page 74 http://viewer.zmags.com/publication/79b53367#/79b53367/74 )

enter image description here

$\endgroup$
15
  • 1
    $\begingroup$ Possible duplicate: mathematica.stackexchange.com/q/22002/121 $\endgroup$
    – Mr.Wizard
    Jun 22, 2013 at 23:00
  • $\begingroup$ @Mr.Wizard I think that it isn´t duplicate, because I don´t want to come back to the start, and the solution is not find the shortest Tour and delete the last "movement" $\endgroup$
    – Mika Ike
    Jun 23, 2013 at 9:08
  • $\begingroup$ I disagree with marking this as duplicate of a TSP question, as well as saying that it already has two answers (which then again are TSP answers). As the o/p said in his comment immediately above mine (this one) and one to my answer, he is NOT looking for a TSP answer, he is looking for an all-pairs shortest path solution. $\endgroup$ Jun 23, 2013 at 10:09
  • $\begingroup$ I agree with @andreas-lauschke. I´m looking fot the shortest (in time, in distance, in dollars,...) path. VISITING ALL VERTEX and NOT COMING BACK TO THE START (NOT A TOUR, YES A PATH). $\endgroup$
    – Mika Ike
    Jun 23, 2013 at 12:27
  • 2
    $\begingroup$ I disagree with @Andreas: This is not an all-pairs shortest path problem, because the path is required to visit all vertices. This really is a minor modification of the travelling salesman problem: all you have to do is create a new vertex, connect it to all the existing vertices via edges of length zero, solve TSP in the augmented graph, and then discard the new vertex and its two edges in the tour you found. This is a standard reduction from Hamiltonian path problems to Hamiltonian cycle problems. I suggest closing as duplicate again. $\endgroup$
    – user484
    Jun 28, 2013 at 18:07

2 Answers 2

8
$\begingroup$

EDIT 1

Now that the question is getting more specific, here another approach:

I'd like to say that this is not a solution, but it shows you how to set-up your graph accordingly. If you combine this with the comment of @Rahul Narain you should get your result easily.

1) Create a PathGraph from the coordinates, with arrow edge style:

arrow[coord_, e_] := Style[Arrow[coord], Red, Thickness[.001], Arrowheads[0.06]]
pg = PathGraph[Range[Length@t], VertexCoordinates -> t, EdgeShapeFunction -> arrow]

enter image description here

2) Create a 10x10 grid:

gg = GridGraph[{10, 10}]

enter image description here

3) Overlay both graphs:

Overlay[{gg, pg}]

enter image description here

4) Let's find the shortest Tour and pick this tour from the coordinate list:

tour = t[[Last[FindShortestTour@t]]]
PathGraph[Range[Length@tour], VertexCoordinates -> t,EdgeShapeFunction -> arrow]

enter image description here

Looks identical to our PathGraph!

Now let's get some shortest paths. For instance the shortest path from vertex 1 to 9:

Overlay[{gg, HighlightGraph[pg, FindShortestPath[pg, 1, 9]]}]

The path is marked with red dots:

enter image description here


Algorithmic Graph Theory -- All-Pairs Shortest Path

As usual, when it is about graph theory I'm using the Combinatorica package that comes with Mathematica.

Using the Combinatorica package you could use several shortest path algorithms.

Let's turn your t into a graph. Your weighting function seems to be nothing else, but an EuclideanDistance. In Combinatorica the EuclideanDistance for graphs is defined as Euclidean:

<< Combinatorica`

g = SetEdgeWeights[FromUnorderedPairs[Flatten[t, 1]], WeightingFunction -> Euclidean]
ShowGraph[g, VertexNumber -> True, VertexNumberPosition -> UpperRight]

enter image description here

Let's get the All-Pairs shortest path:

(s = AllPairsShortestPath[g]) // Short

==> {{0,0.618034,<<6>>,1.23607,0.618034},<<8>>,{<<1>>}}

Please have a look at here for further Floyd-Warshall algorithm discussion

Let's get the Euclidean shortest paths from vertex 1 to all other vertices, by producing a shortest-path spanning tree:

t = ShortestPathSpanningTree[g, 1];
ShowGraphArray[{g, t}, VertexNumber -> True, VertexStyle -> Disk[0.05]]

enter image description here

Let's turn this into an ordered graph:

op = ToOrderedPairs[g];
ShowGraph[FromOrderedPairs@op, VertexNumber -> True, VertexNumberPosition -> UpperRight]

enter image description here

Ordered this graph will have a different spanning tree, so let's run again a shortest-path spanning tree:

t = ShortestPathSpanningTree[g, 1];
ShowGraphArray[{g, t}, VertexNumber -> True, VertexStyle -> Disk[0.05]]

enter image description here

$\endgroup$
8
  • $\begingroup$ But I can´t see the "Short" Hamiltonian Path. It´s a cuais-tree $\endgroup$
    – Mika Ike
    Jun 28, 2013 at 19:50
  • $\begingroup$ Behause there is no? Define please cuais-tree. Why aren't you as specific in your question? $\endgroup$
    – Stefan
    Jun 28, 2013 at 20:06
  • $\begingroup$ I´m looking for a Hamiltonian path (the most economic), and in yous answer I can´t see hamiltonian paths. It´s only that $\endgroup$
    – Mika Ike
    Jun 28, 2013 at 20:10
  • $\begingroup$ cuais-tree? The paths are most economic considering Euclidean distance...please refine your question though! $\endgroup$
    – Stefan
    Jun 28, 2013 at 20:13
  • $\begingroup$ What I want is to Find the Solution to this problem img822.imageshack.us/img822/905/qwu9.png I starting using the code provided by other friend of this forum t = {{{2, 1}, {5, 2}}, {{7, 1}, {9, 4}}, {{9, 2}, {6, 6}}, {{5, 4}, {2, 3}}, {{4, 5}, {7, 9}}, {{8, 5}, {2, 4}}, {{3, 7}, {7, 7}}, {{4, 8}, {1, 10}}, {{3, 10}, {10, 7}}, {{9, 10}, {9, 8}}}; t2t = Table[{If[i != j, Sqrt[(t[[j, 1, 1]] - t[[i, 2, 1]])^2 + (t[[j, 1, 2]] - t[[i, 2, 2]])^2], Infinity], i, j}, {i, 10}, {j, 10}]; t2tlist = Flatten[t2t, 1]; t2tlistsorted = SortBy[t2tlist, First] $\endgroup$
    – Mika Ike
    Jun 28, 2013 at 20:22
4
$\begingroup$

Finding the shortest paths between any s and t is usually called the "all-pairs shortest path" problem, as any is generally interpreted as all. You can do that with the JFloyd function in JVMTools. It can compute the all-pairs shortest distances (guaranteed optimal, this is no heuristic) for thousands of nodes in a few seconds, as that page above shows. Unlike the Dijkstra algorithm, which you could in theory call sequentially to solve this, the function JFloyd also accepts negative arc costs (as long as there are no negative cycles in the network).

I would avoid the term "tour" in this context, as it would point towards the TSP, closed or open. Paths are different from tours, and if I understand you correctly (please correct me if I'm wrong), you want the all-pairs shortest path solutions, no tours. If you want an open TSP solution, just solve the TSP and ignore the edge that closes from end back to start.

Disclosure: I am the owner of Lauschke Consulting, which is the business that sells JVMTools commercially.

$\endgroup$
1
  • $\begingroup$ Yes, I want to visit all vertex (1-10) but without coming back to the start. I think that the solution is not to find the Shortest-Tour and delete the last "edge". $\endgroup$
    – Mika Ike
    Jun 23, 2013 at 9:11

Your Answer

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

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