Find the shortest path between two nodes in a graph in Prolog

Question

I want to find the shortest path between two nodes in Prolog. I figured how to find all the paths between two nodes, but unfortunately the following code falls into loops:

arc(a,b).
arc(b,a).
arc(b,c).
arc(c,b).
arc(c,d).
arc(d,c).

path(X,Y,[arc(X,Y)]) :-
   arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :-
   arc(X,Z),
   path(Z,Y,P).

The code run is:

?- path(a,c,R).
R = [arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, c)] ;
R = [arc(a, b), arc(b, a), arc(a, b), arc(b, a), arc(a, b), arc(b, c)] 
....

So, my question is : How to get all paths without looping infinitely?

at the end of the day, i will get the length of the list and find the minimum.

Please if possible, give solutions that are ISO Prolog.

Note: here is the updated code, by I still have problem. Apparently the member predicate doesn't work when checking against a fact rather than an atom.

xxx([]).

path(X,Y,[arc(X,Y)]) :-
   arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :- 
        arc(X,Z)
        ,xxx(L)
        ,member(arc(X,Z),L)->
            !;
            (member(arc(Z,X),L)->
                !;
                (append(L,[arc(X,Z)],R),retract(xxx(_)),assert(xxx(R)),path(Z,Y,P))).

and my member predicate is:

member(X,[X|T]).
member(X,[H|T])  :-  member(X,T). 

Thank you.

Answer 1

We use meta-predicate path/4 in combination with the definition of arc/2 that you gave:

?- path(arc,Path,From,To).
  From = To        , Path = [To] 
; From = a,  To = b, Path = [a,b]
; From = a,  To = c, Path = [a,b,c]
; From = a,  To = d, Path = [a,b,c,d]
; From = b,  To = a, Path = [b,a]
; From = b,  To = c, Path = [b,c]
; From = b,  To = d, Path = [b,c,d]
; From = c,  To = b, Path = [c,b]
; From = c,  To = a, Path = [c,b,a]
; From = c,  To = d, Path = [c,d]
; From = d,  To = c, Path = [d,c]
; From = d,  To = b, Path = [d,c,b]
; From = d,  To = a, Path = [d,c,b,a]
; false.

The definition of path/4 excludes all cycles.

To get the shortest paths we need to look at all solutions!

To show this is actually so, let's expand your definition of arc/2 like this:

arc(a,b).
arc(b,a).
arc(b,c).
arc(a,c).               % (new)
arc(b,d).               % (new)
arc(c,b).
arc(c,d).
arc(d,c).

Let's say we want to "get all shortest paths from a to d", so we query:

?- path(arc,Path,a,d).
  Path = [a,b,c,d]
; Path = [a,b,d]        % shortest path #1
; Path = [a,c,b,d]
; Path = [a,c,d]        % shortest path #2
; false.

In above query there are two distinct shortest paths from a to d.

To get both, we must look at all paths---or use a smarter meta-predicate (left as homework).