Member Avatar for xinwei

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
  • 624 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by xinwei
Member Avatar for Taywin

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 by Taywin because: n/a
Member Avatar for xinwei

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 ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.