# Assignment: Dijkstra algorithm, find All paths

**URL:** <https://swi-prolog.discourse.group/t/assignment-dijkstra-algorithm-find-all-paths/1588>\
**Category:** Help!\
**Tags:** how-to\
**Created:** [December 9, 2019, 12:39am UTC](https://swi-prolog.discourse.group/t/assignment-dijkstra-algorithm-find-all-paths/1588 "2019-12-09T00:39:17Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Hazel](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/hazel/32/763_2.png) [@Hazel](https://swi-prolog.discourse.group/u/Hazel)\
**Post date:** [December 9, 2019, 12:39am UTC](https://swi-prolog.discourse.group/t/assignment-dijkstra-algorithm-find-all-paths/1588/1 "2019-12-09T00:39:17Z")

</div>

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

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