3

What I want to get is: the path which connect all the points in my graph, but without having to tell the algorithm where to start and where to finish.

It need to use the driving direction in google-maps api but without setting a start or end point.

It is not the TSP problem because I don't have a "start city" and I don't have to get back to the "start city" neither.

As expressed in this question: Find the shortest path in a graph which visits certain nodes, I could just use permutation because I have a few nodes, but the problem is that I need to analyze several groups of this few nodes So I would like the function to be the less time consuming posible.

NOTE: Im not looking for a Minimum Spaning Tree as this one neither: https://math.stackexchange.com/questions/130863/connecting-all-points-on-a-plane-with-shortest-path-possible I want a path which tell me you will save gas if you go first here, then overthere, then overthere, and finally there.

Question: is there any library which can help me with that? Or is it a know problem that has already an exact answer? How could I solve it?

Community
  • 1
  • 1
Laggel
  • 1,356
  • 3
  • 19
  • 36
  • 1
    Yes this is a well known class of problem called "Travelling salesman problem" and it is proved to be NP hard so sorry buddy no luck, consider using hadoop cluster. – specialscope Oct 26 '12 at 01:45
  • what is the real question behind this? why google-maps api. if you have a GIS consider OSM data which you can batch query :) – Karussell Oct 28 '12 at 17:39
  • **The question is:** _How to find the Shortest Path between all the nodes in a graph without having a pre-defined start or end points?_ -- it doesn't has to be with google-maps api I just want to know if there is a way of finding that path. PS Didnt really get how getting osm data can help me to solve the problem. – Laggel Nov 01 '12 at 13:24

4 Answers4

3

It sounds like you want an all pairs shortest path algorithm. This is the class of shortest path algorithms that attempt to compute the shortest path (or the length of the shortest path) between every pair of vertices in the graph.

These is a well-known problem, and solutions exist. Here's some reading material that describes other possible algorithms. There might be implementations of Johnson's algorithm for your chosen language and development environment.

Keep in mind, this is an expensive problem, computationally speaking.

Gian
  • 13,735
  • 44
  • 51
  • 1
    NOP, I don't want the _all pairs_ SPA which as you said it is a well-known problem. The question is: **How to find the Shortest Path between all the nodes (A PATH WHICH INCLUDES ALL THE NODES) in a graph without having a pre-defined start or end points?** – Laggel Nov 01 '12 at 13:26
  • Oh, I see. That's a slightly different question. In that case, is your graph complete? And does it obey the triangle inequality? – Gian Nov 01 '12 at 23:00
0

If I understand you correctly, you want 1 route to visit all the nodes, without a predefined start/end and you want that to be minimal. A possible solution could be to modify your graph a bit to allow a travelling salesman algorithm to get a complete tour.

You start with your graph and add 1 extra node E. You connect that node to all other nodes in your graph and set the cost of all those edges to a very high constant M. You then unleash a travelling salesman algorithm on that graph which will give you a path P starting at E, passing all nodes and returning to E. If you remove the 2 edges in P that connected E to the rest of your path you will have what you were looking for.

A quick intuitive proof that it is indeed what you were looking for: Suppose it's not the cheapest way to connect all nodes. Let's call the supposedly better path Q. Q and P both connect all nodes in your original graph. The end points of Q would be A and B. Both of these would be connected to node E with an edge of cost M. If you would add those 2 edges to Q, you would get a better TSP solution than P, which is not possible as P was the best.

Origin
  • 2,009
  • 5
  • 19
  • 19
0

As you are using google map, your particular instance of TSP might satisfy the Triangle inequality. Are you really speaking of distances or travel time ?

In the case of distances: try Googling: "triangle traveling salesman problem"

IMPORTANT: The result is a very good approximation of the best result with guaranteed uper bound, not always the best.

user2346536
  • 1,464
  • 2
  • 21
  • 43
0

One way to go would be using (self-organized) kohonen networks.
Assume you have n cities on a map (works the same in any dimension).
Take a chain of n connected "neurons" and place it randomly on the map. Then you do several iterations, one iteration contains:

  1. choose any city. (e.g. go through them in a ordered fashion)
  2. determine the "closest" neuron, call it x. (e.g. euclidian distance)
  3. Move this x closer to the city (e.g. take the direction vector from the neuron to the city and multiply it with a learning rate 0
  4. Move neighbors of this neuron also towards this city (but less than in 3., dependend of distance from the neighbors to the "current closest" neuron x)

One can choose various functions in step 2, 3 and 4.

Notice also that this might not give the globally shortest path since it depends on where the start chain is located and different other things. For this on may consider doing several runs with different starting conditions or (depending of the problem) one can help a bit with pre-knowlege.

I hope this helps to complete this question for further readers...

Snow bunting
  • 1,120
  • 8
  • 28