/**/

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).

traverse(From, End, _, [edge(From, End, C)]) :-
    edge(From, End, C).
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).

path(From, To, Path) :-
    traverse(From, To, [], Path).

cost([edge(From, To, Cost)], Cost) :-
    edge(From, To, Cost),
    !.
cost([edge(From, To, Icost)|Tpath], Cost) :-
    cost(Tpath, Tcost),
    edge(From, To, Icost),
    Cost is Icost + Tcost.

shortestPath(From, To, Path) :-
    findall([Cost, Cpath], (path(From, To, Cpath), cost(Cpath, Cost)), Paths),
    sort(Paths, [Spath|_]),
    nth0(1, Spath, Path).