Segundo Bratko, pode-se encontrar caminhos de custo mínimo num grafo colocando-se pesos nos caminhos. O custo de um caminho é a soma das arestas do caminho percorrido até se chegar no vértice atual.
O código utilizado para encontrar caminhos num grafo é apresentado abaixo (Bratko, 2a edição, página 230).
% path ( A, Z, Graph, Path, Cost) - Path é um caminho acíclico (não forma círculos) com custo Cost partindo-se de A a Z no Graph
% e(X, Y) - Representa a existência de uma aresta que parte de X e vai até Y.
adjacent ( X, Y, graph( Nodes, Edges ) :-
member( e(X, Y), Edges)
;
member(e(X, Y), Edges).
path (A, Z, Graph, Path, Cost) :-
path1( A, [Z], 0, Graph, Path, Cost).
path1( A, [A | Path1], Cost1, Graph, [A | Path1], Cost1).
path1 ( A, [Y | Path1], Cost1, Graph, Path, Cost) :-
adjacent ( X, Y, CostXY, Graph),
not member(X, Path1),
Cost2 is Cost1 + CostXY,
path ( A, [X, Y | Path1], Cost2, Graph, Path, Cost).
Este procedimento pode ser utilizado para encontrar um caminho de custo mínimo. Pode-se encontrar tal caminho entre dois nós, node1 e node2 num grafo Graph pelas seguintes metas:
path ( node1, node2, Graph, MinPath, MinCost),
not ( path(node1,node2,Graph,_,Cost), Cost<MinCost).
Mas o autor mesmo cita que está técnica é muito ineficiente para se encontrar um caminho de custo mínimo. Pois este método percorre sucessivamente todos os caminhos possíveis e isto é completamente inaceitável devido a alta complexidade do problema.