在DLV中寻找最短路径

Question

我试图用DLV找到最小距离的图中的所有路径。假设我有以下图表：

​

​

我期望获得谓词(我希望不要跳过任何谓词)：

• 路径(a，b，1)，路径(a，d，1)，路径(a，e，1)，路径(a，c，2)
• 路径(b，a，1)，路径(b，c，1)，路径( d，d，2)，路径(b，e，2)
• 路径(c，b，1)，路径(c，e，1)，路径(c，a，2)，路径(c，d，3)
• 路径(d，a，1)，路径(d，b，2)，路径(d，e，2)，路径(d，c，3)
• 路径(e，a，1)，路径(e，c，1)，路径(e，d，2)，路径(e，b，2)

我想你可以走左边或右边的拱门。因此，我尝试了以下几点：

path(X, Y, 1) :- arc(X, Y).
path(Y, X, 1) :- arc(X, Y).
path(X, Z, L) :- path(X, Y, M), path(Y, Z, N), 
                 X!=Z, 
                 L = M + N,
                 not path(X, Z, V), V < L, #int(V) 

第三条规则的思想是添加2条现有的路径，如果它们不返回(X!=Z)，并且已经没有一条路径连接相同的边与较短的距离(非路径(X，Z，V)，V< L，#int(V))。我不得不添加#int(V)，因为否则规则是不安全的。我不知道是否有更好的方法用整数来解决这个安全问题。

当我运行这段代码(使用标志-N=5设置#maxint=5)时，我得到了不应该存在的路径，例如路径(d，a,5)。我不知道问题是否与#int(V)或其他什么有关，但我不希望这些路径出现，因为我已经有了路径(d，a,1)。可能是因为#int(V)，但我想不出如何正确地做到这一点。

有人能帮我解决这个问题吗？提前谢谢。

Answer 1

来自DES发行版的示例/spaths.dl。见下面的注释代码..。-

%
% Shortest Paths in a Graph
%
% Datalog Formulation
%
% Program: Shortest paths in a graph
% Author : Fernando Sáenz-Pérez
% Date   : September, 2009

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

path(X,Y,1) :- 
  edge(X,Y).
path(X,Y,L) :-
  path(X,Z,L0),
  edge(Z,Y),
  count(edge(A,B),Max),
  L0<Max,
  L is L0+1.

spaths(X,Y,L) :-
   min(path(X,Y,Z),Z,L).


% Note that the following is not stratifiable in DES

%sp(X,Y,1) :- 
%  edge(X,Y).
%sp(X,Y,L) :-
%  sp(X,Z,L0),
%  not(shorter(X,Z,L0)), 
%  edge(Z,Y),
%  L is L0+1.

%shorter(X,Y,L) :-
%  sp(X,Y,L0),
%  L0<L.