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.


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

% check if X has been visited
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),

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


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...

Edited 5 Years Ago by Taywin: n/a

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 ?

This article has been dead for over six months. Start a new discussion instead.