We're a community of 1076K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,075,949 Members — Technology Publication meets Social Media

# prolog graph

Hi, I have an undirected graph, I wish to find 3 shortest paths,
my code below gives me all possible paths,
can anyone give me some advice to find 3 shortest paths ?

my idea of finding 3 shortest path is
1) since i have all possible path, i can store all of them in a list, sort by its length,
choose the 3 shortest.
2) edit my algorithm to give me 3 shortest path.

But I have no idea on how to con't.

``````edge(1,2)
.
.
.

% makes the graph bidirectional
connectedEdge(X,Y) :- edge(X,Y).
connectedEdge(X,Y) :- edge(Y,X).

% check if X has been visited
member(X,[X|R]).
member(X,[Y|R]) :- member(X,R).

% search
path(Node, Node, _, [Node]).
path(Start, Finish, Visited, [Start | Path]) :- connectedEdge(Start, X),
not(member(X, Visited)),
path(X, Finish, [X | Visited], Path).

find_paths(Start, Finish) :- path(Start, Finish, [Start], Path),
printPath(Path),
nl,
fail.

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

thanks.

2
Contributors
2
Replies
18 Hours
Discussion Span
1 Year Ago
Last Updated
3
Views
xinwei
Newbie Poster
10 posts since Aug 2011
Reputation Points: 19
Skill Endorsements: 0

Hmm... How about you keep 3 shortest path values. Each time you get to the end of the search, check with them. If it is shorter than any of the values, replace the value. At the end of all search, you print out these values? Sorry that I can't help you with the code because it's been so long time I touched prolog...

Taywin
Posting Maven
2,633 posts since Apr 2010
Reputation Points: 275
Skill Endorsements: 17

I need to print out the nodes for the 3 shortest path i get, can advice how i maintain 3 shortest path length and the path list together ?

xinwei
Newbie Poster
10 posts since Aug 2011
Reputation Points: 19