在 Openlink Virtuoso 知识图中获取加权最短路径

Question

背景

给定一个具有以下结构的KG

<distanceTo:1> <weight>              3               .
<distanceTo:1> <weight>              4               .

<a>            <distance_with_weight> <distanceTo:1> .
<distanceTo:1> <goes_to>              <b>            .
<b>            <distance_with_weight> <distanceTo:2> .
<distanceTo:2> <goes_to>              <c>            .

我想说，

a

和

c

之间有一条路径，权重为

3 + 4 = 7

。

问题

有没有办法使用SPARQL或SPARQL-BI计算加权最短路径？

我知道有

TRANSITIVE

和

T_SHORTEST

子句，但据我了解，它们仅适用于简单的边缘（没有权重）。

我知道我可以枚举所有路径并取最小权重总和，但这是不可取的，因为在这种情况下，SSSP Dijkstra 算法可能会更快。

到目前为止我所拥有的

SELECT ?t, total_weight
WHERE {
  <a> <distance_with_weight>/<goes_to>* ?t.
  # here I need the sum of the weights involved so that I can get the minimum later.
}

Answer 1

我不知道SPARQL-BI，所以也许有一个解决一般问题的方法，但是如果你的图是一棵树，也就是说，如果有一条从一个点到另一个点的唯一路径，那么纯SPARQL解决方案就可以工作。这个解决方案的部分灵感来自于Joshua Taylor对另一个问题的回答：

PREFIX rdf:     <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs:    <http://www.w3.org/2000/01/rdf-schema#>

SELECT ?destination (SUM(?weight) AS ?total_weight) WHERE { 
  <a> (<distance_with_weight>/<goes_to>)*/<distance_with_weight> ?d .
  ?d <weight> ?weight .
  ?d <goes_to>/(<distance_with_weight>/<goes_to>)* ?destination .
}
GROUP BY ?destination

当图不是树（或森林）时，2个点之间可以存在多条路径，这样查询将添加所有路径的所有权重。循环也有问题，但最多不过是多条路径。最后，数据需要完整，为所有

<distanceTo:i>

节点分配权重，并且对于每对 (

<a>

,

<b>

)，必须有一个不同的

<distanceTo:i>

节点。