This is a classical case for iterative deepening. Just enter at the toplevel:
?- length(Path, N), path(0, 2, Path).
The first answer will be of shortest length. And that's what you can do in Prolog very elegantly: You are starting to enumerate an infinite set, hoping that you will find what you are searching for after a finite amount of time.
Since probably all paths of that length are of equal interest to you, you want all of them. Otherwise, you be happy with above.
Also, you might enumerate the shortest paths for different nodes, so node/1
should be the nodes occurring in your graph. Say, you have nodes 0 to 10, then node/1
could be defined as:
node(N) :-
between(0,10,N).
shortest(A,B, Minpath) :-
setof(Min, Path ^ ( node(A), node(B),
once( ( length(Path, Min), path(A, B, Path) ) ) ), [Min]),
length(Minpath, Min),
path(A, B, Minpath).
However this solution has a catch ; a very ugly catch, indeed. You said:
(however many there are)
In case there is no path at all, this solution will loop forever. You have been warned.
Edit: For completeness: I assumed that path/3
terminates if the length of the list is fixed.
And to conclude: For a concrete simple graph a more explicit method avoiding cycles is preferable. However, there are many situations where it is not clear at all what a cycle actually is (think of simulating some simple machine), and in such situations, iterative deepening is incredibly effective: No clever thinking in your head, just using the power of Prolog.
There is a final note about looping in case there is no path at all. To overcome this problem you need some kind of resource bounded computation. SICStus Prolog offers library(timeout)
, other systems have more or less comparable functionality. SWI (recently) introduced call_with_inference_limit/3
(with a quite arcane interface) to this end.