split_evenly([],[],[]). split_evenly([X],[X],[]). split_evenly([X1,X2|XS], [X1|L1], [X2|L2]) :- split_evenly(XS,L1,L2). merge([],[],[]). merge([],[X|XS],[X|XS]). merge([X|XS],[],[X|XS]). merge([X|XS],[Y|YS],[X|ZS]) :- X=Y, merge([X|XS],YS,ZS). merge_sort([],[]). merge_sort([X],[X]). merge_sort([X1,X2|XS],L) :- split_evenly([X1,X2|XS], H1, H2), merge_sort(H1,SH1), merge_sort(H2,SH2), merge(SH1,SH2,L). connects(a,b,1). connects(a,d,3). connects(b,c,2). connects(c,e,6). connects(c,g,3). connects(d,e,5). connects(e,f,7). connects(f,g,0). % rules to support shortest_path(a,g,W) => W=6 path_from(A,B,W) :- connects(A,B,W). path_from(A,B,W) :- connects(A,C,W1), path_from(C,B,W2), W is W1 + W2. min([X],X). min([X,Y|XS], MIN) :- X=Y, min([Y|XS],MIN). shortest_path(A,B,W) :- setof(P,path_from(A,B,P),L), min(L,W). % rules to support shortest_path(a,g,W,P) => W=6, P=[a,b,c,g] path_from(A,B,W,[A,B]):- connects(A,B,W). path_from(A,B,W,P):- connects(A,C,W1), path_from(C,B,W2,P2), P = [A|P2], W is W1 + W2. min_pair([paired(W,P)],W,P). min_pair([paired(W1,P1),paired(W2,_)|Rest],W,P):- W1=W2, min_pair([paired(W2,P2)|Rest],W,P). shortest_path(A,B,W,P):- setof(paired(W1,P1),path_from(A,B,W1,P1),L), min_pair(L,W,P).