我是neo4j的新手,并试图了解如何优化路由查询。
我和OSM db一起工作。
我试图计算出从一个点到另一个点的距离。
START a=node(760119)
MATCH path=(a)-[:NEXT|NODE*1..30]-(c)
WHERE HAS(c.node_osm_id) AND c.node_osm_id=283103898
RETURN DISTINCT reduce(
distance = 0, n in filter(
x in path where has(x.length)
) | distance + n.length
) A
我正在创建一个程序,它将计算未加权图中所有节点的Betwenness中心性。要做到这一点,我必须找到ASSSP (所有单一源最短路径)。在创建程序时,我意识到最终我将有联系(从源到目的地的距离相同,但路径不同)。这使我想到了这个问题。我该如何解决这些关系?如果我使用随机的断线器,那么对于相同的输入,中间中心度的每个输出可能略有不同。让我做一个小小的示范性图:
A
/ \
B C
\ /
D
现在假设A节点是我们希望找到ASSSP的源。可见,有两条路径(A->B->D和A->C->D),bot的长度相同,两者最短。现在我应该选择哪一个,在什么条件
我试图在有一百万个节点的图中找到最短的路径。平均而言,每个节点可能有20个有向边,因此相当大。
除此之外,有没有一种实时(动态)调整边缘权重的方法?
我的意思是,我想要通过一个时间参数来路由图。根据这个时间参数,它将边权值乘以一定的量。
您可能有以下数据:
节点A
节点B
边1 (A至B)有重量5
边2(也从A到B)有重量3
我可以调用一个函数:
graph.getShortestPath(A, B, 8) // From node A to B at 8am
graph.getShortestPath(A, B, 16) // From node A to B at
我正在看。
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
// part 1
for each vertex v
dist[v][v] ← 0
// part 2
for each edge (u,v)
dist[u][v] ← w(u,v) // the weight of the edge (u,v)
// part 3
for k from 1 to |V|
for i from 1 to |V|
for j from 1 to |V|
如何使用Floyd-Warshall算法获得从顶点1到顶点10的每条具有相同权重的最短路径?我设法得到了从顶点1到顶点10的所有最短路径的总数。
public static int[][] shortestpath(int[][] adj, int[][] path, int[][] count) {
int n = adj.length;
int[][] ans = new int[n][n];
copy(ans, adj);
// Compute incremently better paths through vertex k.
for (i