0

I am searching for a way to determine the path with the lowest cost for connecting different coordinates on a map. These coordinates are representing the consumers of a piping network and one supplier

I was first searching on the GIS part of stack overflow to do a least cost path analysis but this is not what I need (I don't find an algorithm that allows to have more than only a begin and end point). I have an algorithm that determines the lowest cost path between all my different coordinates but now I want to do a sort of critical path analysis on this data. But one where all coordinates have to be addressed in the final solution and where it is not important which coordinate comes first except of the supplier which needs to be the first one.

Can anybody help me with this?

Thanks in advance

Example

OK, the main problem would be:

I'll be have a matrix like this:

  A  B  C  D

A x  3  4  2

B 3  x  7  5

C 4  7  x  9

D 2  5  9  x

In this matrix A, B, C and D would represent a position on a map (just by X and Y coordinates) and the numbers are the prices to make the connection between A and B (ex: these costs are based on data that I would have). My goal is to get all these points connected in any way that is the cheapest way to do it.

To do this, I was thinking about a critical path analysis (that you maybe know from your business classes) but apparently this will not work as these algorithms are not written result in a path that contains all positions. But I need to connect all these (4) nodes, but just in the cheapest way.

For example: When I would take A as starting point, I would need this to result in:

make connection A-D-B-C (this would cost 2+5+7 = 14)

and not

ABCD = 19

ACBD = 16

ADCB = 18

ABDC = 17

ACDB = 18

Peter Vanvoorden
  • 181
  • 1
  • 2
  • 11
  • 1
    I do not understand the question. Can you rephrase it? – Lajos Arpad Apr 01 '14 at 11:39
  • In general you can use Dijsktra's algorithm, where you apply the distance used in your geometrical model and if necessary, modify thee algorithm according to your needs. I do not understand your exact problem, so unless you rephrase your question (you can do that by clicking on the edit button below the tags in your post) this is all I can do for you. – Lajos Arpad Apr 01 '14 at 12:42
  • I putted an example in the problem framing. Hope that makes it more clear. – Peter Vanvoorden Apr 01 '14 at 12:45

1 Answers1

1

The problem you are describing is the problem of the postman, without knowing which is the starting point. From your question I believe that your graph is not directed, so the distance from A to B is congruent to the distance from B to A. In this case, you can solve your problem by iterating all combinations of your points and calculating the total distance (that is, the sum of the distances in the path). The minimum value is the solution of the problem.

Here you can read more about generating the combinations. But do not generate them in advance, that's not good for memory management, just always calculate the next combination, measure its total distance and compare it to the minimum. If its lower than the minimum, modify the minimum distance to the new minimum and store the combination into an array which will contain the optimal path at the end. This is the end of the answer if your graph is undirected and all node-pairs have a vertice.

If I am wrong and your graph is directed, then it's not enough to generate all the combinations, you will need to generate all variations instead.

Note, that if for some reason it might be a case when a node-pair not necesarily has a vertice. In this case you need to generate all the valid variations, where valid means that two nodes near each-other has a vertice.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175