PROLOG：图中最长的路径

Question

我有这个算法用于图形中的最短路径，但现在我需要调整它以获得最长的路径，我的意思是，边值较高的路径

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]|_].

有什么帮助吗？

谢谢

Answer 1

如果 sort/2 将它们按最短的顺序排列，那么最长的应该是 Sorted 中的最后一个条目。

见last/2, append/3, and (more expensively) reverse/2。

PROLOG：图中最长的路径

PROLOG: longest path in graph

graph

prolog