Branch and Bound Shortest Path in Prolog

Branch and bound shortest path algorithm can be implemented with restart . The algorithm doesn't use any dynamic database only backtracking and recursion. Lets say we have this graph:


Which we can represent in Prolog as these facts:

% edge(-Vertex, -Vertex)
edge(a, b).         edge(a, c).
edge(a, d).         edge(b, c).
edge(c, d).         edge(c, e).
edge(d, e).

We first need a bounded path finder. This can be realized as a predicate that takes an upper bound, and then returns the number of hops subtracted from the upper bound, with the guarantee that the result is never below zero:

% path(+Vertex, +Vertex, +Integer, -Integer)
path(X, X, N, N).
path(X, Y, N, M) :- N > 0,
   H is N-1,
   edge(X, Z),
   path(Z, Y, H, M).

The bounded path finder is non-deterministic and uses backtracking for its search. We now add a further predicate that restarts the path finder by recursively using a smaller upper bound, whenever a path was found. This way the smallest length is

% bb_path(+Vertex, +Vertex, +Integer, -Integer)
bb_path(X, Y, N, M) :- N > 0,
   H is N-1,
   path(X, Y, H, K), !,
   L is H-K,
   bb_path(X, Y, L, M).
bb_path(_, _, N, N).

Note the use of a cut in the predicate branch and bound predicate. Here is an example run. We start with an upper bound which is the number of edges plus one. We can first manually call path/4 multiple times and simulate the search:

?- path(a, e, 7, K), L is 7-K.
K = 3,
L = 4 
?- path(a, e, 3, K), L is 3-K.
K = 0,
L = 3 
?- path(a, e, 2, K), L is 2-K.
K = 0,
L = 2 
?- path(a, e, 1, K), L is 1-K.
No

So starting with an upper bound 8, we gradually get better upper bounds 4, 3 and 2, until no more improvements are possible. The predicate bb_path/4 does this search for us:

?- bb_path(a, e, 8, X).
X = 2