加权图的最短路径

Question

我想创建一个网络优化模型，使用概率分布来代替节点之间权重的单一估计。为了开始，我写了一个Python脚本，在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()

这个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

试试这个查询，这应该对你有用。

首先，你需要获取从起始节点到目标节点的路径，然后调用 REDUCE 函数，设置一个初始值为0的累加器。接下来，我们会遍历这个路径中的所有元素，查看它们之间的关系。REDUCE 函数会对集合中的每个元素执行管道符后面的表达式，因此我们需要用到r，并将所有的距离加起来。最后，我们按照总距离进行排序，这样就能显示从节点228068到节点228077的最短路径了……

Patrick