我想创建一个网络优化模型,该模型使用概率分布而不是节点之间权重的单点估计。首先,我编写了一个 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 脚本创建以下图表:
从长远来看,我的目的是从真实的旅程中迭代地采样成本/时间,以便了解如何通过网络最好地运送 cargo ,以及可以预期什么样的服务水平。它实际上是通过加权网络的最短路径的蒙特卡罗模拟。
我是 Neo4j 新手,尝试编写最短路径 Cypher 查询:
START beginning=node(228068), end=node(228077)
MATCH p = shortestPath(beginning-[*..500]-end)
RETURN p
它通过网络返回以下路径:
查询返回的通过网络的路线不是距离最短的路线。我想顶点之间的边的权重是相等的。
您能看出需要对 Cypher 查询执行哪些操作才能按距离对最短路径进行加权吗?
最佳答案
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。我们运行集合(路径)并得到看一下关系,REDUCE
将在集合的每个元素上运行管道笔划后面的表达式,因此我们需要 r 并对所有距离求和。最后但并非最不重要的一点是,我们按总距离排序,它将显示从节点 228068 到节点 228077 的最短路径...
帕特里克
关于python - 加权图的最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26458589/