It is clear from a glance at the original diagram that there are several routes from a to b. One way of making sure that we have found all possible routes is to use some form of notation to record the several routes possible from a to b. One such method is to draw a tree of the possible routes with each branching point in the tree corresponding to a node in the original network.

Looking at the diagram, you should first satisfy yourself that this search tree does indeed include each complete route of the network. You should also notice that, once a path has been taken, the paths never later rejoin. For instance, the right-hand branches of node 1 in the tree and of node 3 are the same, but drawn separately in the tree. Of course, if we did rejoin diverging routes, we would end up with a network which would be exactly the one drawn in the first place.

This diagram is a representation of all the possibilities when searching the network for the routes. It might therefore be called a "search tree". It is theoretically possible to draw search trees of all logic programming queries or goals, but problems with large search trees (sometimes called large "search spaces") are tedious to draw and expensive of paper.

Looking at the tree, how do we know which is the shortest route between a and b? It is easy to see that there are two, both toward the right-hand side of the tree. But how could we find either the shortest route, the route that always takes the first node on or after "twelve o'clock" of each node in the network, or all the routes? To do these, we must have a method of working through the search tree.

 The starting node is:
 
 

     Stage           Node   Route so far
     1               a     a

     Stage           Node   Route so far
     1.1             1     a -> 1

          1.3                           6          a  ->   6
 
 

We go to the third level and list the alternatives:
 
 

     Stage           Node   Route so far
     1.1.1           2     a -> 1 -> 2

          1.2.1                        4          a  ->  3  ->  4

          1.2.2                        7          a  ->  3  ->  7

          1.3.1                        7          a  ->  6  ->  7

          1.3.2                        9          a  ->  6  ->  9
 
 

We go to the fourth level and list the alternatives:
 
 

     Stage           Node   Route so far
     1.1.1.1         5     a -> 1 -> 2 -> 5

          1.2.1.1                     5          a  ->  3  ->  4  ->  5

          1.2.2.1                     8          a  ->  3  ->  7  ->  8

          1.2.2.2                     b          a  ->  3  ->  7  ->  b

          1.3.1.1                     8          a  ->  6  ->  7  ->  8

          1.3.1.2                     b          a  ->  6  ->  7  ->  b

          1.3.2.1                     b          a  ->  6  ->  9  ->  b
 
 

We go to the fifth level and list the alternatives:
 
 

     Stage           Node   Route so far
     1.1.1.1.1       8     a -> 1 -> 2 -> 5 -> 8

          1.2.1.1.1                  8          a  ->   3 ->  4  ->  5  -> 8

          1.2.2.1.1                  b          a  ->   3 ->  7  ->  8  -> b

          1.3.1.1.1                  b          a  ->   6 ->  7  ->  8  -> b
 
 

The sixth level is the final level:
 
 

     Stage           Node   Route so far
     1.1.1.1.1.1     b     a -> 1 -> 2 -> 5 -> 8 -> b

          1.2.1.1.1.1               b          a  ->  3  ->  4  ->  5  ->  8  -> b
 
 

Looking at the fourth level we can see that the shortest routes are found first. We could decide to stop when we had found the first solution (1.2.2.2) or to go on to found all possible solutions.  
 

The starting node is:  
 

     Stage           Node   Route so far
     1               a     a

     Stage           Node   Route so far
     1.1             1     a -> 1

     Stage           Node   Route so far
     1.1.1           2     a -> 1 -> 2

     Stage           Node   Route so far
     1.1.1.1         5     a -> 1 -> 2 -> 5

     Stage           Node   Route so far
     1.1.1.1.1       8     a -> 1 -> 2 -> 5 -> 8

     Stage           Node   Route so far
     1.1.1.1.1.1     b     a -> 1 -> 2 -> 5 -> 8 -> b

     Stage           Node   Route so far
     1.1.2           4     a -> 1 -> 4
                

As was demonstrated above, the strategy is not connected to the way in which the program is written. It should be possible to write a description of the problem that is to be solved without reference to the strategy that will be used to apply the program. Thus a logic program can be said to be a specification of the solution to a problem. This stands in contrast to most languages which are heavily procedural, which is to say that languages like Pascal, COBOL, Fortran, BASIC C, C++ and so on include not only information about the problem being solved but also how that information must be applied and when.

Prolog is an instance of a logic programming language and therefore has to decide which strategy it is going to use to "execute" the logical statement of the problem. Prolog uses the depth-first strategy (method 2) and has some extensions to make it work more efficiently on current sequential computers. These notes makes a distinction between "Pure Prolog" (which is the logic programming heart of Prolog) and the whole of Prolog (which includes extra-logical extensions). A later module shows how a Pure Prolog interpreter can be written in Prolog, and can be made to work either depth-first or breadth-first.