How to find shortest path in prolog with weighted graph

Question

I have this code :

link(a,b,4). 
link(a,c,2). 
link(b,g,5). 
link(c,g,6). 
link(c,d,5). 
link(d,g,3). 

path(S,D,TDist):- 
    link(S,D,TDist). 
path(S,D,TDist):- 
    link(S,X,TD1), path(X,D,TD2), TDist=TD1+TD2. 

This will follow a depth first search strategy, but the result is that it will give me all the paths, and it won't show which is the shortest. Is it possible to still use that strategy and find the shortest path? if not, what search strategy to use? and how can I implement it.

Answer 1

I think there are problems with your code:

• TDist=TD1+TD2 doesn't compute the sum, use is/2 instead, at least when a path is returned.

• It will loop if the graph contains cycles, but assuming the data actually is a DAG, we can ignore by now.

• We can't say what the actual path will be, just its value.

Anyway, library(aggregate) can be used to find the shortest path. For instance

?- aggregate(min(D), path(a,g,D), D).
D = 8.

Or, since gnu-prolog doesn't have library(aggregate), take the first element computed by setof/3:

?- setof(D, path(a,g,D), [Min|Rest]).
Min = 8,
Rest = [9, 10].