search all paths and the shortest path for a graph - Prolog
Posted
by prologian
on Stack Overflow
See other posts from Stack Overflow
or by prologian
Published on 2010-04-01T22:22:06Z
Indexed on
2010/04/01
22:23 UTC
Read the original article
Hit count: 815
Hi , I have a problem in my code with turbo prolog wich search all paths and the shortest path for a graph between 2 nodes the problem that i have is to test if the node is on the list or not exactly in the clause of member and this is my code :
/*
1 ---- b ---- 3
--- | ---
--- | -----
a |5 d
--- | -----
--- | ---
2 --- | --- 4
-- c --
for example we have for b--->c
([b,c],5) , ([b,a,c],3) and ([b,d,c],7) : possible paths.
([b,a,c],3) : the shortest path.
*/
DOMAINS
list=Symbol *
PREDICATES
distance(Symbol,Symbol)
path1(Symbol,Symbol,list,integer)
path(Symbol,Symbol,list,list,integer)
distance(Symbol,list,integer)
member(Symbol,list)
shortest(Symbol,Symbol,list,integer)
CLAUSES
distance(a,b,1).
distance(a,c,2).
distance(b,d,3).
distance(c,d,4).
distance(b,c,5).
distance(b,a,1).
distance(c,a,2).
distance(d,b,3).
distance(d,c,4).
distance(c,b,5).
member(X, [Y|T]) :- X = Y; member(X, T).
absent(X,L) :-member(X, L),!,fail.
absent(_,_).
/*find all paths*/
path1(X, Y, L, C):- path(X, Y, L, I, C).
path(X, X, [X], I, C) :- absent(X, I).
path(X, Y, [X|R], I, C) :- distance(X, Z, A) , absent(Z, I),
path(Z, Y, R, [X|I] ,C1) , C=C1+A .
/*to find the shortest path*/
shortest(X, Y, L, C):-path(X, Y, L, C),path(X, Y, L1, C1),C<C1.
© Stack Overflow or respective owner