Hello,
I have an assignment using Dijkstra algorithm.
This algorithm allows me to calculate a single optimal path of a graph, but, i
wish to calculate all paths that use a time not exceeding a certain given limit without modifying the algorithm(but using it). I have no idea how to do that in Prolog.
Here is my code.
> % Here we are at the end of our path (to)
> dijkstra([Time-[To|RPath] |_], To, [To|RPath], Time) :- !.
>
> % We look for the best candidate then we start again
> dijkstra(Visited, To, RPath, Time) :-
> best_candidate(Visited, BestCandidate), % au debut, Visited est une liste contenant notre etat de depart.
> dijkstra([BestCandidate|Visited], To, RPath, Time).
>
> % Calculation of the best candidat
> best_candidate(VisitedPaths, BestCandidate) :-
> findall( %find all the potential paths of the current state.
> CheminPotentiel,
> ( member(Len-[State1|Path], VisitedPaths),%for the current state in paths,
> arc(State1, State2, Time), %see the possible paths
> \+ is_visited(VisitedPaths, State2),%If state 2 has not been visited
> NewTime is Len + Time, %then we calculate the new temp.
> CheminPotentiel = NewTime-[State2,State1|Path] %add the POTENTIAL path state1 to state2 to the list of paths.
> ), % With the new Time added by this way.
> Candidates
> ),
>
> minimum(Candidates, BestCandidate). %on a besoin de tout les candidats ne depassend pas la limite
>
> %Minimum of a list
> % Here, keysort sorts a list key -> [value] according to key. He then extracts the smallest
> % table (Min).
> % ex: minimum([0-[3,2], 4-[1]], M). ----> M = 0-[3, 2].
> minimum(List, Min) :-
> keysort(List, [Min|_]).
> %member(Chemin,List).
>
> % Check if a summit has been visited
> % Here, State represents a state in a room. every state can be is visited, or not yet.
> % memberchk checks if there is a pair of the form _- [U | _] in the Paths path list.
> is_visited(VisitedPaths, State) :-
> memberchk(_-[State|_], VisitedPaths).
This is my principal predicate
> shortest_path(From, To, Path, Time) :- > dijkstra([0-[From]], To, RPath, Time), > reverse(RPath, Path).
I have tried
findall(Path,shortest_path(From, To, Path, Time),PathList).
member(X,PathList).
But X gives me the same paths multiple times… not sure whats going on (The algorithm works for sure.)
Thankyou.