论文标题
评估最短的路径语义下的常规路径查询
Evaluating regular path queries under the all-shortest paths semantics
论文作者
论文摘要
本报告的目的是解释如何修改教科书广度优先搜索算法（BFS），以便创建一个将单个源节点连接到可从中获得的所有节点的所有最短路径的紧凑表示。通过这种表示，所有这些路径也可以有效地列举。然后，我们将此算法应用于在边缘标记的图中解决类似问题，在该图形图中，路径还具有附加的限制，即它们的边缘标签形成一个属于常规语言的单词。也就是说，我们解决了在最短的路径语义下评估常规路径查询（RPQ）的问题。
The purpose of this report is to explain how the textbook breadth-first search algorithm (BFS) can be modified in order to also create a compact representation of all shortest paths connecting a single source node to all the nodes reachable from it. From this representation, all these paths can also be efficiently enumerated. We then apply this algorithm to solve a similar problem in edge labelled graphs, where paths also have an additional restriction that their edge labels form a word belonging to a regular language. Namely, we solve the problem of evaluating regular path queries (RPQs) under the all-shortest paths semantics.
