Find the shortest path in between nodes

Help!
1

I’m using: SWI-Prolog version 8.0.3

I want the code to: Find the shortest path in between nodes placeA to placeH

My code looks like this:

node(placeA, placeB, 11).
node(placeA, placeC, 26).
node(placeA, placeD, 37).
node(placeA, placeE, 13).
node(placeA, placeF, 96).
node(placeB, placeE, 73).
node(placeB, placeC, 14).
node(placeC, placeD, 5).
node(placeC, placeH, 24).
node(placeD, placeH, 71).
node(placeE, placeG, 123).
node(placeG, placeH, 20).
node(placeF, placeH, 29).

The 3 parameter is the distance between the nodes.
I cant figure this out, i tried diferent things, but with no sucess, i am new to prolog aswell

2

I guess, you would want to look up one shortest path algorithm, analyze it, and then try to translate it into prolog.

This is what i found when doing a google search: shortest path between two nodes:

Dan

3

This problem looks NP-complete to me. Should be easily reductible to
the HAMILTON PATH problem.

If that’s the case, a brute force approach could be tried. This would
entail the use of foreach.

Cheers
Volker

4

If this is homework, I imagine you’re not supposed to use tabling or some of the other libraries that would make this easier, but here’s a naive solution using tabling:

EDIT: can also do it here without tabling, just using order_by/2. Still a pretty naive solution, so probably not what the assignment actually wants.

:- module(shortpath, [test/2]).

:- use_module(library(solution_sequences), [order_by/2]).
:- use_module(library(lists), [reverse/2]).

node(placeA, placeB, 11).
node(placeA, placeC, 26).
node(placeA, placeD, 37).
node(placeA, placeE, 13).
node(placeA, placeF, 96).
node(placeB, placeE, 73).
node(placeB, placeC, 14).
node(placeC, placeD, 5).
node(placeC, placeH, 24).
node(placeD, placeH, 71).
node(placeE, placeG, 123).
node(placeG, placeH, 20).
node(placeF, placeH, 29).


%:- table(path(_, _, _, min)).

path(A, B, [B, A], C) :- node(A, B, C).
path(A, B, [B|Ps], Cost) :-
    node(C, B, Cost1),
    path(A, C, Ps, Cost0),
    Cost is Cost0 + Cost1.

test(Path, Cost) :-
    order_by([asc(Cost)],
             ( path(placeA, placeH, Path0, Cost),
               reverse(Path0, Path) )).

Example output:


?- test(P, C).
P = [placeA, placeB, placeC, placeH],
C = 49 ;
P = [placeA, placeC, placeH],
C = 50 ;
P = [placeA, placeB, placeC, placeD, placeH],
C = 101 ;
P = [placeA, placeC, placeD, placeH],
C = 102 ;
P = [placeA, placeD, placeH],
C = 108 ;
P = [placeA, placeF, placeH],
C = 125 ;
P = [placeA, placeE, placeG, placeH],
C = 156 ;
P = [placeA, placeB, placeE, placeG, placeH],
C = 227.