Table modes are useful for the declarative description of dynamic programming problems [6,20]. The following program encodes the Dijkstra's algorithm, which is for finding the minimum-weight path between a pair of nodes.
:-table sp(+,+,-,min). sp(X,Y,[(X,Y)],W) :- edge(X,Y,W). sp(X,Y,[(X,Z)|Path],W) :- edge(X,Z,W1), sp(Z,Y,Path,W2), W is W1+W2.
The predicate edge(X,Y,W) defines a given weighted directed graph, where W is the weight of the edge from node X to node Y. The predicate sp(X,Y,Path,W) states that Path is a path from X to Y with the smallest weight W. Note that, whenever the predicate sp/4 is called, the first two arguments are always instantiated. Therefore, only one answer is tabled for each pair.
Note that, if table modes are not respected, or if there is no bound for an optimized argument, a program may give unexpected answers. For example, if the weights of some edges are negative, then there will be no lower bound for the optimized argument; hence, the program will never stop.
Consider a variant of the problem, where the goal is to find a shortest path among the paths that have the minimum weight for each pair of nodes. The following gives a program:
:-table sp(+,+,-,min). sp(X,Y,[(X,Y)],(W,1)) :- edge(X,Y,W). sp(X,Y,[(X,Z)|Path],(W,Len)) :- edge(X,Z,W1), sp(Z,Y,Path,(W2,Len1)), Len is Len1+1, W is W1+W2.
Since only one argument can be optimized, a compound term, (W,Len), is used in order to denote the optimized value, where W is the weight of a path, and Len is the length of the path. Note that the order is important. If the term would be (Len,W), the program would find a shortest path, breaking ties by selecting a path that has the minimum weight.
The cardinality limit of a tabled predicate can be dynamically changed by using the built-in table_cardinality_limit.
Neng-Fa Zhou 2013-01-25