Skip to content

Instantly share code, notes, and snippets.

Created September 5, 2017 16:40
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
findapath(X, Y, W, [X,Y], _) :- edge(X, Y, W). % findapath between X and Y has weight W if there is an edge between X and Y of weight W
findapath(X, Y, W, [X|P], V) :- % else findapath between X and Y
\+ member(X, V), % is true
edge(X, Z, W1), % if we can findapath between X and Z with weight W1
findapath(Z, Y, W2, P, [X|V]), % and there is findapat between Z and Y of weight W2
W is W1 + W2. % where W is W1 + W2
findminpath(X, Y, W, P) :-
\+ solution(_, _),
findapath(X, Y, W1, P1, []),
assertz(solution(W1, P1)),
!, findminpath(X,Y,W,P).
findminpath(X, Y, _, _) :-
findapath(X, Y, W1, P1, []),
solution(W2, P2),
W1 < W2,
retract(solution(W2, P2)),
asserta(solution(W1, P1)), fail.
findminpath(_, _, W, P) :- solution(W,P), retract(solution(W,P)).
main :-
write('the minimum cost that we must pay.'),
write('path that has the minimum cost.'),
nl, halt.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment