How to find a unique shortest path for a weighted directed graph using SWI Prolog?

Question

This is an extension of what I did in the Prolog class. In the class, I was asked to write the path(X, Y, N) predicate path(X, Y, N) , which returns true if there is only a path from node X to node Y with a length of N A list of directed edges with corresponding weights is given, for example. edge(a, b, 3) and edge(c, d, 10) .

This problem is quite simple (only some recursions and basic cases). However, I thought that perhaps I could expand this a bit further. Given that a simple oriented graph entry can contain cycles and contains only non-negative weights, what is the length of the unique shortest path from given nodes A and B (The only thing I mean is that this predicate should return false if there is more than one shortest path from A to B ).

Here is an example database that contains a loop (a, b, c, e, a).

 edge(a, b, 1). edge(b, c, 2). edge(c, d, 1). edge(b, d, 4). edge(c, e, 1). edge(e, a, 10). edge(e, d, 6). 

I thought that in order to satisfy a single condition, I thought that I should increase the initial predicate path/3 to also contain the path information in the form of a list (so that later we could compare the uniqueness of the path). This new increase is reflected in the new path/4 predicate.

 path(X, X, 0, []). path(X, Y, N, [Y]) :- edge(X, Y, N). path(X, Y, N, [Z|T]) :- edge(X, Z, N1), N2 is N - N1, N2 > 0, path(Z, Y, N2, T). path(X, Y, N) :- path(X, Y, N, _). 

As in this code, I already found the problem: if I try to combine the predicate with path(a, b, N, Z) , this will not work, because N will not be able to combine with N2 is N - N1 . However, if I change this part to N is N1 + N2 , it still won't work, because N2 is still not unified. If I changed the entire predicate line to:

 path(X, Y, N, [Z|T]) :- edge(X, Z, N1), path(Z, Y, N2, T), N is N1 + N2. 

This will work endlessly, because the number of paths is probably endless, because the graph may contain loops (which I want to try to save as a call).

Regarding the predicate shortestpath/3 , I cannot find all the paths and check if all the paths are longer, because the number of paths can be infinite due to the presence of a loop. Instead, I tried to find paths that have a length from 0 to a given N ; if there is no way, then this is by far the shortest way.

 countdown(N, N). countdown(N, X) :- N1 is N - 1, N1 >= 0, countdown(N1, X). shortestpath(A, B, N) :- path(A, B, N), \+((countdown(N, N1), N > N1, path(A, B, N1))). 

However, this does not apply to N defined as a variable (since the countdown function does not work), not to mention the only restriction.

So my question is, is there a way to make this question work, or is it really impossible to do? If there is such a solution, please report it here (or, if you think this is a homework question, please at least direct me in the right direction).

Limitations:

• I do not want to use built-in predicates. For example, there are only “simple” or “basic” predicates, such as \+ , is , + . var , nonvar , asserta and similar predicates are also somewhat acceptable (since there is no alternative that provides the same functionality).

• I want it to be as general as possible; that is, any arguments for the predicate should be able to give as a variable. (or at least the last argument to shortestpath/3 , which is the length of the shortest path, a variable).

---

I have already considered the following questions and did not answer my situation:

• Find the shortest path between the two nodes in the graph in Prolog (does not apply to weighted edges, and also uses complex predicates (e.g. path/4 )).

• Search all paths and the shortest path for a chart - Prolog (does not consider charts with cycles).

• Find the shortest path between two nodes in the graph in (Prolog) and display the result as an array (does not apply to weighted edges).

Please feel free to point me to any other question that relates to my question.

Answer 1

It's nice to ask a question based on homework, not just homework! Let's start with your predicate and see if we can beat it into submission, and then talk about some alternative approaches.

First, I start with a simplified predicate from yours:

 path(X, Y, N, [XY]) :- edge(X, Y, N). path(X, Z, N, [XY|T]) :- edge(X, Y, N0), path(Y, Z, N1, T), N is N0 + N1. 

The main difference here is that I just generate paths and then calculate lengths. I'm not doing subtraction here. It is well known that in Prolog you can start with the simplest method of generating and testing, and then refine either the generator or the test, or both, until you are happy, so this is just a simple generator. I save both the source and destination nodes in the path sequence to just help me visualize what is happening, and with it you immediately see the problem with loops:

 ?- path(a, e, N, T). N = 4, T = [ab, bc, ce] ; N = 18, T = [ab, bc, ce, ea, ab, bc, ce] ; N = 32, T = [ab, bc, ce, ea, ab, bc, ce, ea, ... - ...|...] . 

I don’t think we are with your example graph, but we could work a little here from the first Prolog search: until there are no failures, Prolog has no reason to back up and try a different way. And you see the cycles right there. If you used breadth-first instead, you would be sure that the first solution is the shortest, simply because, advancing everything by one step, you never end up in a rabbit hole before creating your first solution. Dijkstra's algorithm (thanks for reminding @JakobLovern) circumvents the problem by coloring the visited nodes and not counting them more than once.

You can control the search behavior by creating a metainterpreter, which is not as bad as it seems, but it is more than setting up a search to account for loops, which I think most people do in this case with a graph, so try again:

 path(X, Y, N, Path) :- path(X, Y, N, [], Path). path(X, Y, N, Seen, [X]) :- \+ memberchk(X, Seen), edge(X, Y, N). path(X, Z, N, Seen, [X|T]) :- \+ memberchk(X, Seen), edge(X, Y, N0), path(Y, Z, N1, [X|Seen], T), \+ memberchk(X, T), N is N0 + N1. 

Adding the Seen parameter and using \+ memberchk/2 to avoid adding things to the path that are already in the path is not really unusual. memberchk/2 not an ISO, but it is a very common predicate. You could implement this yourself (don't do this!):

 memberchk(X, L) :- once(member(X, L)). member(X, [X|_]). member(X, [_|Xs]) :- member(X, Xs). 

I find it worth noting that memberchk/2 + lists are basically equal to the sets used in Dijkstra's algorithm. This is similar to in in Python; it would be crazy to try to do something real in Prolog, at least member/2 .

These changes make path/4 avoid the loops, so now you can find all the solutions without any false. Note I have not made your schedule acyclic. I just made path/4 loop knowledge.

Note that we get several solutions:

 ?- path(a, d, X, Y). X = 5, Y = [a, b] ; X = 4, Y = [a, b, c] ; X = 10, Y = [a, b, c, e] ; false. 

There is a good library, aggregate , which is useful for such situations. But you did not ask for false libraries. :)

Let’s just get the shortest path:

 uniq_shortest_path(X, Y, MinCost, Path) :- path(X, Y, MinCost, Path), \+ (path(X, Y, LowerCost, OtherPath), OtherPath \= Path, LowerCost =< MinCost). 

This literally says that Path is the shortest path between X and Y (which has a MinCost value) if and only if there is no other path with a value less than or equal to our value. Attempt:

 ?- uniq_shortest_path(a, d, MinCost, Path). MinCost = 4, Path = [a, b, c] ; 

This trick is not cheap; it probably works by comparing all solutions to each other. But it works, without any additional fraud.

Significant improvement is likely to be achieved by obtaining all decisions, sorting by cost and then ensuring that the first two do not have the same value before reporting the cost and path of the first.

A more significant improvement could probably be found by executing Dijkstra's algorithm directly or, perhaps, by trying to make the first meta-interpreter. Performing an iterative-deepening approach is likely to work, but I doubt it will work better since it often has to do and repeat all the work leading to a result that is priced too expensive.

Anyway, I hope this helps! Be delighted with the Prologue!