%branch and bound

caminho_bb(O,D,C):-
    caminho_bb2(D,[(0,[O])],C).

%valida se o destino ja se encontra na lista de listas visitados
caminho_bb2(D,[(_,[D|L])|_],[D|L]).

% V e o valor somado de todos os valores dos ramos e depois e feito a
% soma desses valores
caminho_bb2(D,[(V,[X|L])|R],Res):-
    findall((NV,[Z,X|L]),(liga(X,Z,Par),not(member(Z,[X|L])),NV is Par+V),Caminhos),
    append(R,Caminhos,F),
    sort(F,F2),
    caminho_bb2(D,F2,Res).
    %ao fazer o sort o caminho com menos custo fica em primeiro