CODEWITHSUNDEEP
prologshortest-path
user2818866
user2818866

Reputation: 35

Prolog need to get it fix

The solution 

ppath(X,Y,M,Path,[Y|Path]) :- edge(X,Y,M), 

\+ memberchk(Y,Path).
path(X,Y,P,SoFar,Path) :- edge(X,W,M), \+ 

memberchk(W,SoFar),
    path(W,Y,N,[W|SoFar],Path), P is M+N.


pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[],P), 

Z).

After that i am trying to use ?- pravilo(a,z,M). get the result. but it says false.

My version SWI-Prolog (Multi-threaded, 64 bits, Version 6.4.1)

Thank You

Upvotes: 2

Views: 369

Answers (1)

CapelliC
CapelliC

Reputation: 60034

You should avoid assert/retract as far as possible.

Your graph has a loop between f and g, then you can't use the naive path/4 predicate, or your program will loop.

To avoid looping, you should invert the path construction (now it's 'bottom up'), to 'top down' adding a further argument (an accumulator) to path/4, and check that a node isn't already visited before recursing.

You can use memberchk for the test.

edit: here is the code

path(X,Y,M,Path,[Y|Path]) :- edge(X,Y,M), \+ memberchk(Y,Path).
path(X,Y,P,SoFar,Path) :- edge(X,W,M), \+ memberchk(W,SoFar),
    path(W,Y,N,[W|SoFar],Path), P is M+N.

this yields

?- path(a,z,W,[],P).
W = 27,
P = [z, e, j, b] ;
W = 26,
P = [z, g, b] ;
...

let's use library(aggregate) to complete the assignment:

pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[],P), Z).

now I get

?- pravilo(a,z,M).
M = 24.

edit To get (full) ordered paths, these changes are necessary in recursion base

path(X,Y,M,Path,FullPath) :-
   edge(X,Y,M), \+ memberchk(Y,Path), reverse([Y|Path], FullPath).

and in top level predicate:

pravilo(X,Y,Z) :-
    aggregate(min(W), P^path(X,Y,W,[X],P), Z).

Upvotes: 1

Related Questions