Find the shortest path in between 2 nodes

Help!
1

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 ?

2

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
3

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
4

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
5

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

6

https://www.swi-prolog.org/pldoc/man?predicate=last/2

1 Like
7

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