在无向图中找到两个顶点之间的最短路径

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.

Answer 1

从你的程序开始，你可以用这段代码解决这个问题：

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

?- shortestPath(1,5,Path,Length).
Length = 3.5,
Path = [1, 2, 5]

如果您不想使用 sort/2（注意 sort/2 会删除重复项），您可以这样写：

shortestPath(X,X,[X,X],0):- !.
shortestPath(X,Y,MinP,MinD):-
    findall([L,P],path(X,Y,P,L),Set),
    splitList(Set,LD,LP),
    min_list(LD,MinD),
    nth1(I,LD,MinD),
    nth1(I,LP,MinP).

splitList([],[],[]).
splitList([[L,D]|T],[L|TP],[D|TD]):-
    splitList(T,TP,TD). 

?- shortestPath(1,5,Path,Length).
    Length = 3.5,
    Path = [1, 2, 5]
    false.

所以基本上，你找到所有的解决方案并选择最小的一个...

在无向图中找到两个顶点之间的最短路径

Find shortest path between two vertices in undirected graph

prolog

shortest-path