/*
 *  Naam      : R. Wacanno
 *  UvAnetID  : 11741163
 *  Studie    : BSc Informatica
 *
 *  solution2.pl
 *  -Contains the solution to opdracht 2.
 */

edge(1, 2, 5).
edge(2, 1, 3).
edge(2, 3, 4).
edge(2, 4, 3).
edge(2, 5, 5).
edge(3, 1, 9).
edge(3, 2, 2).
edge(5, 1, 3).
edge(5, 4, 2).

/* True if an edge exists between From and End directly. */
traverse(From, End, _, [edge(From, End, C)]) :-
    edge(From, End, C).
/* True if an intermediate edge exists between From and Inter leading to To.
   This edge should not be contained in the list Visited. */
traverse(From, To, Visited, [edge(From, Inter, C)|Path]) :-
    edge(From, Inter, C),
    \+ member(edge(From, Inter, C), Visited),
    Inter \== To,
    traverse(Inter, To, [edge(From, Inter, C)|Visited], Path).

/* True if Path is a list of edges from From to To*/
path(From, To, Path) :-
    traverse(From, To, [], Path).

/* True if Cost is the cost of the single edge contained in the given list. */
cost([edge(_, _, Cost)], Cost).
/* True if Cost is de addition of the head and tail cost. */
cost([edge(_, _, Icost)|Tpath], Cost) :-
    cost(Tpath, Tcost),
    Cost is Icost + Tcost.

/* True if Path is the path with the lowest cost from From to To. */
shortestPath(From, To, Path) :-
    findall([Cost, Len, Cpath],
            (path(From, To, Cpath), cost(Cpath, Cost), length(Cpath, Len)),
            Paths),
    sort(Paths, [[_, _, Path]|_]).