Prolog :- shortest path through ALL points?

Zw0nE99
Zw0nE99 used Ask the Experts™
on
Hello!

I need a program (written in prolog) which outputs THE SHORTEST path through oriented graph (all points) which are defined like this:

conn(a,a,1).
conn(a,b,3). <- you can travel only from a to b but not from b to a
conn(a,c,10). conn(c,a,10).<- this means that you can travel in both directions between a and c
conn(b,c,5).

etc... (program naturally has to work with larger amount of points - let's say about 100 different points). Path should start and end in same point.
connections are defined as
conn(point1,point2,distance_between_point1_&_point2)

No need to optimize the program to run fast so I would appreciate the simpliest possible solution so I can understand and modify it then (I'm not very good in prolog programming)

I would appreciate output something like this (in this case):

?- tracepath(Length,Path).
Length=18, Path=[a,b,c,a]

where length is the distance we travelled and path is the order of points we visited. In this case we travel only through points in alphabetical order. But program has to work also let's say with following set of points:

conn(a,a,1).
conn(a,c,10). conn(c,a,10).
conn(b,c,5). conn(c,b,5).

?- tracepath(Length,Path).
Length=30, Path=[a,c,b,c,a]

Thanx for any help!
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Commented:
Hello,

This is well known problem and you can try to find an answer in the following sources:

   http://kti.ms.mff.cuni.cz/~bartak/prolog/graphs.html#search
   http://cs.chonbuk.ac.kr/~jdyang/lecture/shortest.ari

I hope that will help.

Regards,
SVik

Author

Commented:
Well second link helped me a little but I after all I managed to write whole thing by myself I just needed an example how this should look since I don't have any experience in Prolog syntax (first link didn't work unfortunatelly). Thanx anyway

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial