python - 通过加权图的最短路径

我想创建一个使用概率分布而不是节点之间权重的单点估计的网络优化模型。首先，我编写了一个Python脚本，在Neo4j中构建了一个示例网络：from py2neo import neo4jimport randomrandom.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查询进行哪些操作才能按距离加权最短路径吗？ 最佳答案 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 totalDistanceORDER BY totalDistance ASCLIMIT 1试试这个查询，这应该适合您。首先，您尝试获取从StartNode到EndNode的路径，然后调用REDUCE函数，设置一个初始值为0的累加器。我们遍历Collection（路径）并查看Relationships，其中将在Collection的每个Element上的Pipe Stroke后面运行Expression，因此我们需要r并求和所有距离。最后但并非最不重要的一点是，我们对totalDistance进行排序，它将显示从节点228068到节点228077的最短路径...帕特里克关于python - 通过加权图的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26458589/