title: Return shortest path with Breadth-first search in prolog
body: <p>I would like to find the shortest route from station A to station B in prolog in bidirectional graph(if A is connected to B than B is connected to A),the graph has no weights on branches. The question is posted like this  </p>
  
  <pre><code>solve(Start,End,Path).
  </code></pre>
  
  <p>Start-starting station.<br>
  End-Destination station.<br>
  Path-List of all stations passed with the shortest route. The distance between any two directly connected stations in the graph is equal.
  fact in base are like this:  </p>
  
  <pre><code>fact("Staion1","metroline","Station2","metroline"). 
  </code></pre>
  
  <p>metro line is the number of line that connects the two staions directly. If 2nd and 4th argument are the same the stations are connected directly.</p>
  
  <pre><code>line("Abbesses","12","Pigalle","12").  
  line("Abbesses","12","Lamarck Caulaincourt","12").  
  line("Ale'sia","4","Mouton Duvernet","4").  
  line("Ale'sia","4","Porte d'Orle'ans","4").  
  line("Alexandre Dumas","2","Philippe Auguste","2").  
  line("Alexandre Dumas","2","Avron","2").  
  line("Alma Marcesu","9","Ie'na","9"). 
  </code></pre>
  
  <p>EDIT:
  I tried to solve the problem and I figure out that it would work faster if use BFS.<br>
  here is the solution that I wrote:   </p>
  
  <pre><code>solve(Start,End,Path):-solve1([Start],End,[Start],Path).   
  
  solve1([P|O],End,Visited,[End|?]):-children(P,S),member(End,S),!.   
  solve1([P|O],End,Visited,Path):-(not(member(P,Visited)),children(P,S),append(O,S,O1),solve1(O1,End,Visited,Path));  
  (solve1(O,End,Visited,Path)).
  </code></pre>
  
  <p>?-should be the list with path to destination Node<br>
  The only problem is that i don't know how to return the path to the destination node.<br>
  Thank's ahead.   </p>