PROLOG：具有最少连接的图形路径

Question

我想知道如何获得连接最少的路径，而不是连接值总和最小的路径。我的知识是：

edge (vertex1, vertex2, value).

谓词应该return路径和连接数。

我有这个谓词，但它计算的是连接之间具有最小值的路径，而不是连接数本身。

path(X,Y,[X,Y],L):- 
    edge(X,Y,L).

path(X,Y,[X|W],L):- 
    edge(X,Z,L1), 
    path(Z,Y,W,L2), 
    L is L1 + L2.
shortestPath(X,X,[X,X],0):- !.
shortestPath(X,Y,MinP,MinD):-
    findall([L,P],path(X,Y,P,L),Set),
    sort(Set,Sorted),
    Sorted = [[MinD,MinP]|_].
%

有什么想法吗？

编辑

我对代码进行了一些更改，但不知道为什么它不起作用

path(X,Y,[X,Y],L):- 
    edge(X,Y,L),
    L is 1.
path(X,Y,[X|W],L):- 
    edge(X,Z,L1), 
    path(Z,Y,W,L2), 
    L is L2 + 1.
shortestPath(X,X,[X,X],0):- !.
shortestPath(X,Y,MinP,MinD):-
    findall([L,P],path(X,Y,P,L),Set),
    sort(Set,Sorted),
    Sorted = [[MinD,MinP]|_].
%

我的知识库是

edge(1,2,10).
edge(1,3,1).
edge(3,2,1).

我想要这个 shortestPath(1,2,X,Y)。给我直接路径 1 -> 2 但我仍然得到 1 -> 3 -> 2.

有人能帮帮我吗？

Answer 1

如果最小连接数是指最短路径，快速解决方法是修复总和而不是计算重量而是计算长度。但是，有更好的方法可以找到没有 findall/3.

的最短路径

无论如何，您会很容易找到大量最短路径的示例。

PROLOG：具有最少连接的图形路径

PROLOG: Graph path with minimum connections

graph

prolog

编辑