Find the shortest path in between 2 nodes

I’m using: SWI-Prolog version 8.0.3

I want the code to: Find the shortest path in between 2 nodes, and print the shortest path

But what I’m getting is: All the paths between 2 nodes

My code looks like this:

``````oh(placeA, placeB, 13)
oh(placeB, placeC, 3)
oh(placeB, placeD, 45)
oh(placeC, placeD, 7)
oh(placeD, placeF, 34)

path(A, B, [A, B], X) :-
oh(A, B, X).
path(A, B, PathAB, Length) :-
oh(A, C, X),
path(C, B, PathCB, LengthCB),
PathAB = [A | PathCB],
Length is X + LengthCB.

find_paths(A, B) :-
path(A, B, Path, Length),
printPath(Path),
writef(' distance %d\n', [Length]),
fail.

printPath([]).
printPath([X]) :-
!, write(X).
printPath([X|T]) :-
write(X),
write(', '),
printPath(T).
``````

What do i have to change in my code to only give me the shortest path ?

Like this:

shortest(A, B) :-
findall(p(Len, Path),
path(A, B, Path, Len),
Paths),
sort(Paths, Sorted),
Sorted = [p(Len1, Path1) | _],
printPath(Path1),
writef(’ distance %d\n’, [Len1]).

Bye
Volker

1 Like

Again:

``````shortest(A, B) :-
findall(p(Len, Path),
path(A, B, Path, Len),
Paths),
sort(Paths, Sorted),
Sorted = [p(Len1, Path1) | _],
printPath(Path1),
writef(' distance %d\n', [Len1]).
``````

Bye
Volker

1 Like

Or (this will get duplicates that are shortest) (untested code):

``````shortest(A, B) :-
findall(Len-Path,
path(A, B, Path, Len),
Paths),
keysort(Paths, Sorted),
Sorted = [ShortestLen-_|_],
setof(Path, member(ShortestLen-Path, Paths), ShortestPaths),
maplist(printPath, ShortestPaths),
format(' distance ~d~n', [Len1]).
``````
1 Like

And if i wanted the the longest path ? can i use sort ?

1 Like

You can also use `order_by/2` from `library(solution_sequences)` to just take the first solution with the smallest length, e.g.

``````shortest(A, B) :-
once(order_by([asc(Cost)], path(A, B, Path, Len))).
``````
1 Like