在DLV中找到最短路径

Question

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

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

• path（a，b，1），path（a，d，1），path（a，e，1），path（a，c，2）
• path（b，a，1），path（b，c，1），path（d，d，2），path（b，e，2）
• path（c，b，1），path（c，e，1），path（c，a，2），path（c，d，3）
• path（d，a，1），path（d，b，2），path（d，e，2），path（d，c，3）
• path（e，a，1），path（e，c，1），path（e，d，2），path（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) 

第三条规则的想法是，如果不回溯（X！= Z），并且不存在连接相同边缘且距离较短的路径（不是path（X，Z，V， ），V

[当我运行此代码（使用标志-N = 5设置＃maxint = 5时）时，我得到的路径不应存在，例如path（d，a，5）。我不知道问题是否出在#int（V）或其他问题上，但我不希望这些路径出现，因为我已经有一个path（d，a，1）。可能是因为#int（V）导致的，但我不知道如何正确执行此操作。

有人可以帮我解决这个问题吗？预先感谢。

Answer 1

使用列表跟踪路径的解决方案：

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.

请注意，我们需要使用谓词
node（）定义所有节点，并且谓词arc（）假定图的边缘是双向的。

Answer 2

examples / spaths.dl来自DES发行版。请参阅下面的注释代码...-

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