通過加權圖的最短路徑

我想創建一個網絡優化模型，使用概率分佈而不是單點估計來計算節點之間的權重。要開始，我寫了建立在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的腳本創建以下圖表：

network graph

從長期來看，我的意圖是反覆樣品費用/次，以瞭解如何通過網絡最佳地路由貨物，以及可以預期什麼樣的服務級別。它實際上是通過加權網絡的最短路徑的蒙特卡洛模擬。

我是新來的Neo4j，並試圖寫的最短路徑查詢Cypher支架：

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

它返回通過網絡以下路徑：通過網絡

not the shortest path

路線查詢返回的距離不是最短的。我想象頂點之間的邊緣被加權平均。

您能否看到需要對Cypher查詢做什麼以便按距離對最短路徑加權？

來源

2014-10-20 Alex Woolford

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

來源

2014-10-20 13:02:58 Patrick

通過加權圖的最短路徑

回答

相關問題