SQL - postgres - 图中的最短路径 - 递归

我有一张表，其中包含节点x到节点和的边的图。SQL - postgres - 图中的最短路径 - 递归

n1 | n2 
------- 
a | a 
a | b 
a | c 
b | b 
b | d 
b | c 
d | e

我想创建一个（物化）图，该表示节点的最短数/跳的路径包含从X到达节点ÿ：

n1 | n2 | c 
----------- 
a | a | 0 
a | b | 1 
a | c | 1 
a | d | 2 
a | e | 3 
b | b | 0 
b | d | 1 
b | c | 1 
b | e | 2 
d | e | 1

应该如何我建模我的表格和视图以促进这一点？我想我需要某种递归，但我认为在SQL中很难完成。我想避免这种情况，例如，如果路径碰巧包含10个节点/跃点，则客户端需要激发10个查询。

来源

2011-07-29 Water Dorst

PostgreSQL 9有[WITH RECURSIVE]（http://www.postgresql.org/docs/9.0/interactive/queries-with.html），但我没有找到数据库内最短的路径。 –

而不是即时计算这些值，为什么不创建一个真正的表与所有有趣的对和最短的路径值。然后，无论何时在数据表中插入，删除或更新数据，都可以重新计算所有最短路径信息。（Perl的Graph模块特别适合执行此任务，而Perl的DBI界面使代码变得简单明了。）

通过使用外部进程，还可以限制重新计算的次数。使用PostgreSQL触发器会导致每次插入，更新和删除都会发生重新计算，但是如果您知道要添加20对点，则可以等到插入完成后再进行计算。

来源

2011-08-01 10:45:14 unpythonic

这对我的作品，但它有点难看：

WITH RECURSIVE paths (n1, n2, distance) AS (
    SELECT 
     nodes.n1, 
     nodes.n2, 
     1 
    FROM 
     nodes 
    WHERE 
     nodes.n1 <> nodes.n2 

    UNION ALL 

    SELECT 
     paths.n1, 
     nodes.n2, 
     paths.distance + 1 
    FROM 
     paths 
     JOIN nodes 
     ON 
      paths.n2 = nodes.n1 
    WHERE 
     nodes.n1 <> nodes.n2 
) 
SELECT 
    paths.n1, 
    paths.n2, 
    min(distance) 
FROM 
    paths 
GROUP BY 
    1, 2 

UNION 

SELECT 
    nodes.n1, 
    nodes.n2, 
    0 
FROM 
    nodes 
WHERE 
    nodes.n1 = nodes.n2

而且，我不知道那将是多么针对大型数据集执行。正如Mark Mann所建议的那样，您可能想要改为使用图库，例如， pygraph。

编辑：这里是与pygraph

from pygraph.algorithms.minmax import shortest_path 
from pygraph.classes.digraph import digraph 


g = digraph() 

g.add_node('a') 
g.add_node('b') 
g.add_node('c') 
g.add_node('d') 
g.add_node('e') 

g.add_edge(('a', 'a')) 
g.add_edge(('a', 'b')) 
g.add_edge(('a', 'c')) 
g.add_edge(('b', 'b')) 
g.add_edge(('b', 'd')) 
g.add_edge(('b', 'c')) 
g.add_edge(('d', 'e')) 

for source in g.nodes(): 
    tree, distances = shortest_path(g, source) 
    for target, distance in distances.iteritems(): 
     if distance == 0 and not g.has_edge((source, target)): 
      continue 
     print source, target, distance

不包括图形的建筑时间的样品，这需要0.3ms的，而SQL版本需要0.5毫秒。

来源

2011-08-01 14:54:21 sayap

扩展Mark的答案，还有一些非常合理的方法来探索SQL中的图形。实际上，它们会比perl或python中的专用库更快，因为数据库索引会让您无需浏览图表。

最有效的索引（如果图不是经常变化的话）是一个名为GRIPP index的嵌套树变体。（链接的文章提到了其他方法。）

如果图形不断变化，您可能需要将nested intervals方法应用于图形，方式与GRIPP扩展嵌套集合类似，或仅使用浮点数而不是整数（不要忘记通过强制转换为数字来恢复它们，如果你这样做的话就回到浮动状态）。

来源

2011-08-01 19:40:28

SQL - postgres - 图中的最短路径 - 递归

回答

相关问题