I have an undirected, unweighted graph, I wish to find 3 shortest paths between

Question

I have an undirected, unweighted graph, I wish to find 3 shortest paths between 2 nodes, as I'm simulating a mrt network thus duplicate path is allowed due to transfer station.
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
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.

[Code]
edge(1,2)
.
.

connectedEdge(X,Y) :- edge(X,Y).
connectedEdge(X,Y) :- edge(Y,X).

member(X,[X|R]).
member(X,[Y|R]) :- member(X,R).

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.

printPath([]).
printPath([X]) :- !, write(X).
printPath([X|T]) :- write(X),write(', '),printPath(T).
[/Code]

Explanation / Answer

creating a ADT , is creating another class. For example class path{ int weight =0; LinkedList paths = new LinkedList(); public path(LinkedList list, n){ weight = n; for(int i = 0; i p.weight //i is the index for the linkedlist. three_shortest.get(0).weight > p.weight //this is for the one shortest path three_shortest.get(1).weight > p.weight //this is for the second shortest path three_shortest.get(2).weight > p.weight //this is for the third shortest path *** note, this does not store the path in sorted weight, therefore u need to compare all three. if you want it to be sorted, you have to implement when you are adding the path to the list. to replace the longest, use three_shortest.set(i, p) where i is the index where it is the longest path among the three shortest path.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---