Path between two vertices in a graph

On backtracking, this procedure will find all paths between two given vertices. Note that to find the shortest path between two vertices, it is more efficient to use Dijkstra's algorithm.

/* path(First, Last, Path, Length) is true if Path is a path of length     */
/*   Length from the First vertex to the Last vertex in the graph defined  */
/*   by e/3.                                                               */
path(First, Last, Path, Length):-
  path_1(First, Last, [], 0, Path, Length).

path_1(Last, Last, Path, Length, [Last|Path], Length).
path_1(First, Last, Path0, Length0, Path, Length):-
  e(NextToLast, Last, Length1), 
  \+member(NextToLast, Path0), 
  Length2 is Length0 + Length1,
  path_1(First, NextToLast, [Last|Path0], Length2, Path, Length).

/* Sample data */
/* e.g. path(a0, a1, Path, Length). */
e(a0,a1,5).
e(a0,a2,3).
e(a0,a4,2).
e(a1,a2,2).
e(a1,a3,6).
e(a2,a1,1).
e(a2,a3,2).
e(a4,a1,6).
e(a4,a2,9).
e(a4,a3,4).

LPA Index     Home Page