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

Question

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

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

我想创建一个(物化) View ，它表示一条路径包含从 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

我应该如何为我的表和 View 建模以促进这一点？我想我需要某种递归，但我相信这在 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 毫秒。