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

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 毫秒。

Answer 2

与其即时计算这些值，不如创建一个包含所有有趣对以及最短路径值的真实表。然后，每当在数据表中插入、删除或更新数据时，您都可以重新计算所有最短路径信息。（Perl 的Graph模块特别适合这项任务，而且 Perl 的DBI界面使代码变得简单。）

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