查找DLV中的最短路径

Question

我正在尝试使用DLV以最小距离查找图中的所有路径。说我有以下图表：

我期待获得谓词（我希望我不要跳过任何）：

• 路径（A，B，1），路径（b，c，1），路径（b，c，1），路径（d，1），路径（a，e，1），路径（a，c，2）
• （c，b，1），路径（c，e，1），路径（c，a，2），路径（c，d，3），路径（b，e，2）
• ）
• path（d，a， （e，a，1），路径（e，c，1），路径（d，b，2），路径（d，e，2），路径（d，c，3）路径（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），#int（V））。我不得不添加#int（V），否则规则不安全。我不知道是否有更好的方法来解决这个整数值的安全问题。当我运行这个代码（带有标志-N = 5来设置＃maxint = 5）时，我得到的路径不应该在那里，例如路径（d，a，5）。我不知道问题是否出现在#int（V）或其他地方，但我不希望这些路径出现，因为我已经有一个路径（d，a，1）。可能是因为#int（V），但我无法弄清楚如何做到这一点。

任何人都可以帮我解决这个问题吗？提前致谢。

Answer 1

example/spaths.dl from DES distribution。请参阅下面的注释代码... -

% 
% 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. 

Answer 2

解决使用列表中的问题跟踪的路径：

path(X, Y, [X, Y], 1) :- arc(X, Y). 
path(Y, X, [Y, X], 1) :- arc(X, Y). 
path(X, Z, P, D) :- path(X, Y, P1, D1), 
        path(Y, Z, P2, 1), 
        #insLast(P1, Z, P), 
        D = D1 + 1, 
        not #member(Z, P1). 
shortest_path(X, Y, D) :- node(X), node(Y), 
          #min{L: path(X, Y, P, L)} = D.     

解决方案，而无需名单（与 CapelliC的帮助）

path(X, Y, 1) :- arc(X,Y). 
path(Y, X, 1) :- arc(X,Y). 
path(X, Y, D) :- path(X,Z,D0), arc(Z,Y), 
        #count{A: node(A)} = Max, 
        D0<Max, X != Y, 
        D = D0+1. 

shorter_paths(X, Y, D) :- node(X), node(Y), 
          #min{L: path(X, Y, L)} = D. 

请注意，我们需要与谓词 节点（）和定义的所有节点的谓词 arc（）假设图的边是双向的。