通过加权图的最短路径

Question

我想创建一个网络优化模型，使用概率分布而不是单点估计来计算节点之间的权重。要开始，我写了建立在Neo4j的样本网络的Python脚本：

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

Python的脚本创建以下图表：

从长期来看，我的意图是反复样品费用/次，以了解如何通过网络最佳地路由货物，以及可以预期什么样的服务级别。它实际上是通过加权网络的最短路径的蒙特卡洛模拟。

我是新来的Neo4j，并试图写的最短路径查询Cypher支架：

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

它返回通过网络以下路径：通过网络

路线查询返回的距离不是最短的。我想象顶点之间的边缘被加权平均。

您能否看到需要对Cypher查询做什么以便按距离对最短路径加权？

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 

试试这个查询，这应该适合你。

首先尝试从StartNode到EndNode的路径，然后调用REDUCE函数，设置一个初始值为0的累加器。我们运行Collection（Path）并查看关系，一个REDUCE将在集合的每个元素上运行Pipe Stroke后面的表达式，因此我们需要r并总计所有距离。最后但并非最不重要，我们ORDER BY totalDistance，它将显示从节点228068到节点228077的最短路径...

Patrick Patrick