使用Clingo实现有向图两节点间距离计算的技术咨询

首先，你当前代码存在一个关键问题：第三行规则edge(X,Y) :- edge(X,Z), edge(Z,Y).会无限递归生成传递边，导致程序无法正常终止——你不应该重定义原始的edge谓词，而应该用单独的谓词（比如reachable）来表示节点间的可达性。

下面是计算最短距离的正确实现方案，避免硬编码距离值：

% 1. 定义所有节点：包含在边中的所有顶点
node(X) :- edge(X,_).
node(Y) :- edge(_,Y).

% 2. 计算节点间的可达性（传递闭包），不修改原始边
reachable(X,Y) :- edge(X,Y).
reachable(X,Y) :- reachable(X,Z), edge(Z,Y).

% 3. 基础情况：直接相连的节点距离为1
distance(X,Y,1) :- edge(X,Y).

% 4. 递推计算更长的距离：仅当没有更短的路径时才生成
distance(X,Y,D+1) :-
    distance(X,Z,D),
    edge(Z,Y),
    not distance(X,Y,D'),
    D' <= D,
    X != Y.

% 5. 约束：确保每个节点对只保留最短的距离
:- distance(X,Y,D1), distance(X,Y,D2), D1 < D2.

% 可选：添加自身到自身的距离为0
distance(X,X,0) :- node(X).

% 显示结果
#show distance/3.

代码解释 #

• 可达性分离：用reachable单独处理传递闭包，避免污染原始的edge事实，防止无限递归。
• 最短距离保证：递推规则中通过not distance(X,Y,D'), D' <= D确保不会生成比已存在路径更短的距离；后续的约束直接排除同一节点对的长距离结果，最终每个(X,Y)对只会保留最短路径的距离。
• 自身距离：可选的distance(X,X,0)规则处理节点到自身的距离，符合常规定义。

示例输入与输出 #

假设输入以下边事实：

edge(a,b).
edge(b,c).
edge(a,c).

运行后会得到以下结果：

distance(a,a,0) distance(b,b,0) distance(c,c,0)
distance(a,b,1) distance(b,c,1) distance(a,c,1)

可以看到，a到c的最短距离是1（直接边），而非通过b中转的2。

内容的提问来源于stack exchange，提问作者Chrizzoh