shortest path through weighted graph

Question

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:

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()

The Python script creates the following graph:

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.

I'm new to Neo4j and attempted to write a shortest path Cypher query:

START beginning=node(228068), end=node(228077) 
MATCH p = shortestPath(beginning-[*..500]-end) 
RETURN p

It returns the following path through the network:

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.

Can you see what needs to be done to the Cypher query in order to weight the shortest path by distance?

Answer 1

START start=node(244667), end=node(244676)
MATCH p=(start)-[:CONNECTS*1..4]->(end)
RETURN p as shortestPath,
REDUCE(distance=0, r in relationships(p) | distance+r.distance) AS totalDistance
ORDER BY totalDistance ASC
LIMIT 1

try this query, this should work for you.

At first you try to get the Path from StartNode to your EndNode, then call the REDUCE function, set an accumulator with the initial value 0. The we run through the Collection (Path) and hav a look at the Relationships, an REDUCE will run the Expression behind the Pipe Stroke on every Element of the Collection, therfor we need the r and sums all distances. Last but not least, we ORDER BY the totalDistance and it will show the shortestPath from Node 228068 to Node 228077...

Patrick