title: Variation on critical path in python
body: <p>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</p>
  
  <p>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.</p>
  
  <p>Can anybody help me with this?</p>
  
  <p>Thanks in advance</p>
  
  <p><strong>Example</strong></p>
  
  <p>OK, the main problem would be:</p>
  
  <p>I'll be have a matrix like this:</p>
  
  <pre><code>  A  B  C  D
  
  A x  3  4  2
  
  B 3  x  7  5
  
  C 4  7  x  9
  
  D 2  5  9  x
  </code></pre>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>For example: When I would take A as starting point, I would need this to result in:</p>
  
  <p>make connection A-D-B-C (this would cost 2+5+7 = 14)</p>
  
  <p>and not </p>
  
  <p>ABCD = 19</p>
  
  <p>ACBD = 16</p>
  
  <p>ADCB = 18</p>
  
  <p>ABDC = 17</p>
  
  <p>ACDB = 18</p>