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

Question

我有一张包含图中从节点x到节点y的边的表格。

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

我希望创建一个（物化）视图，它表示从x到节点y的路径包含的最短节点/跳数：

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个查询。

- Water Dorst

---

PostgreSQL 9拥有WITH RECURSIVE，但我不知道如何在数据库中查找最短路径。 - mu is too short

Answer 1

这个方法对我来说可行，但有点丑：

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.3毫秒，而SQL版本则需要0.5毫秒。

- sayap

Answer 2

在马克的回答基础上，也有一些非常合理的方法可以在SQL中探索图形。事实上，它们将比perl或python中的专用库更快，因为DB索引将使您不必探索图形。

如果图形不经常更改，则最有效的索引（称为GRIPP索引的嵌套树变体）速度最快。（链接的论文提到了其他方法。）

如果您的图形经常更改，您可能希望以类似于GRIPP扩展嵌套集的方式来调整嵌套区间方法以适应图形，或者简单地使用浮点数而不是整数（如果这样做，请不要忘记通过强制转换为数字并再次转换为浮点数进行标准化）。

- Denis de Bernardy

Answer 3

不妨创建一个具有所有有趣对及其最短路径值的实际表，而不是即时计算这些值。然后，每当在数据表中插入、删除或更新数据时，您可以重新计算所有最短路径信息。(Perl 的 Graph 模块非常适合此任务，并且 Perl 的 DBI 接口使代码简单明了。)

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

- unpythonic