title: shortest path through weighted graph
body: <p>I'd like to create a network optimization model that uses probability distributions instead of single-point estimates for the weights between nodes. To get started, I wrote a python script that builds a sample network in Neo4j:</p>
  
  <pre><code>from py2neo import neo4j
  import random
  
  random.seed(1234)
  
  def makeGraph():
      graph_db = neo4j.GraphDatabaseService()
      graph_db.clear()
      location = graph_db.get_or_create_index(neo4j.Node, "LOCATION")
      loss = graph_db.get_or_create_index(neo4j.Relationship, "LOSS")
      fromToLoss = []
      fromToLoss.append(('start', 'm', random.gammavariate(alpha=3, beta=1)))
      fromToLoss.append(('start', 'n', random.normalvariate(mu = 5, sigma = 0.5)))
      fromToLoss.append(('start', 'o', random.gammavariate(alpha=6, beta=0.5)))
      fromToLoss.append(('m', 'p', random.gammavariate(alpha=5, beta=0.5)))
      fromToLoss.append(('n', 'p', random.gammavariate(alpha=7, beta=0.5)))
      fromToLoss.append(('n', 'q', random.gammavariate(alpha=6, beta=0.5)))
      fromToLoss.append(('o', 'q', random.normalvariate(mu = 5, sigma = 0.5)))
      fromToLoss.append(('p', 'r', random.gammavariate(alpha=6, beta=0.5)))
      fromToLoss.append(('p', 's', random.gammavariate(alpha=6, beta=0.5)))
      fromToLoss.append(('q', 's', random.normalvariate(mu = 6, sigma = 0.4)))
      fromToLoss.append(('q', 't', random.gammavariate(alpha=6, beta=0.5)))
      fromToLoss.append(('r', 'end', random.normalvariate(mu = 5, sigma = 0.5)))
      fromToLoss.append(('s', 'end', random.gammavariate(alpha = 5, beta=0.7)))
      fromToLoss.append(('t', 'end', random.normalvariate(mu = 5, sigma = 0.5)))
      for edge in fromToLoss:
          vertexFrom, vertexTo, loss = edge
          fromLocation = location.get_or_create('LOCATION', vertexFrom, {'location':vertexFrom})
          toLocation = location.get_or_create('LOCATION', vertexTo, {'location':vertexTo})
          path = fromLocation.get_or_create_path(("CONNECTS", {"distance": loss}), toLocation)
  
  makeGraph()
  </code></pre>
  
  <p>The Python script creates the following graph:</p>
  
  <p><img src="https://i.stack.imgur.com/FCe1W.png" alt="network graph"></p>
  
  <p>Longer term, my intention was iteratively sample costs/times from real legs of the journey in order to understand how to best route goods through the network, and what sort of service levels can be expected. It's effectively a Monte Carlo simulation of the shortest path through a weighted network.</p>
  
  <p>I'm new to Neo4j and attempted to write a shortest path Cypher query:</p>
  
  <pre><code>START beginning=node(228068), end=node(228077) 
  MATCH p = shortestPath(beginning-[*..500]-end) 
  RETURN p
  </code></pre>
  
  <p>It returns the following path through the network:</p>
  
  <p><img src="https://i.stack.imgur.com/3ds0N.png" alt="not the shortest path"></p>
  
  <p>The route through the network that's returned by the query is not the shortest one in terms of distance. I imagine that the edges between the vertices are being weighted equally.</p>
  
  <p>Can you see what needs to be done to the Cypher query in order to weight the shortest path by distance?</p>