Retour chemin le plus court avec la largeur-première recherche dans prolog

Question

Je voudrais trouver le chemin le plus court de la station A à la station B en prologue dans le graphique bidirectionnel (si A est connecté à B que B est connecté à A), le graphique pas de poids sur les branches. La question est postée comme ceci
solve (Start, End, Path).
Station de départ.
Station de destination finale.
Path-List de toutes les stations passées avec l'itinéraire le plus court. La distance entre deux stations directement connectées dans le graphique est égale. fait dans la base sont comme ceci:
fait ("Staion1", "metroline", "Station2", "metroline").
ligne de métro est le numéro de ligne qui relie directement les deux staions. Si les 2ème et 4ème arguments sont identiques, les stations sont directement connectées.

ligne ("Abbesses", "12", "Pigalle", "12").
ligne ("Abbesses", "12", "Lamarck Caulaincourt", "12").
ligne ("Ale'sia", "4", "Mouton Duvernet", "4").
ligne ("Ale'sia", "4", "Porte d'Orle'ans", "4").
ligne ("Alexandre Dumas", "2", "Philippe Auguste", "2").
ligne ("Alexandre Dumas", "2", "Avron", "2").
ligne ("Alma Marcesu", "9", "Ie'na", "9").

EDIT: J'ai essayé de résoudre le problème et j'ai compris que cela fonctionnerait plus rapidement si vous utilisez BFS.
Voici la solution que j'ai écrite:
solve (Début, Fin, Chemin): - solve1 ([Démarrer], Fin, [Démarrer], Chemin).

solve1 ([P | O], Fin, Visité, [Fin |?]): - enfants (P, S), membre (Fin, S),!.
solve1 ([P | O], Fin, Visité, Chemin): -
(pas (membre (P, visité)), enfants (P, S), append (O, S, O1), resol1 (O1, End, Visited, Path));
(solve1 (O, Fin, visité, chemin)).
? -doit être la liste avec le chemin d'accès au nœud de destination
Le seul problème est que je ne sais pas comment retourner le chemin vers le nœud de destination.
Merci à l'avance.

Answer 1

Vous pouvez utiliser l'algorithme de Dijkstra.

http://en.wikipedia.org/wiki/Dijkstra « s_algorithm